构图+SPFA求最短路即可，只不过代码很长。
通过这道题目我发现数组模拟链表比动态内存分配构建链表快得多！
以下是我的代码：
#include<stdio.h>
#include<string.h>
#define maxn 307
#define INF 510000007
FILE *fin=fopen("message.in","r"),*fout=fopen("message.out","w");
typedef struct
{
long v,w,next;
}edge;
typedef struct
{
long count,front,rear,item[maxn*maxn*10];
}queue;
const long xd[]={-1,-1,0,1,1,1,0,-1},
yd[]={0,1,1,1,0,-1,-1,-1};
long n,m,x,y,k,c[3];
long r[maxn][maxn],a[maxn][maxn];
long first[maxn*maxn],count;
edge e[maxn*maxn*10];
queue q;
long d[maxn*maxn];
bool inq[maxn*maxn];
void Clear()
{
q.count=0;q.front=0;q.rear=-1;
}
void Push(long x)
{
q.count++;q.rear++;q.item[q.rear]=x;
}
void Pop(long &x)
{
q.count--;x=q.item[q.front];q.front++;
}
bool Empty()
{
return (q.count==0);
}
long f(long _x,long _y)
{
return (_x-1)*m+_y;
}
void input()
{
fscanf(fin,"%ld%ld%ld%ld%ld%ld%ld\n",&n,&m,&x,&y,&k,&c[1],&c[2]);
c[0]=0;
for(long i=1;i<=n;i++)
{
for(long j=1;j<=m;j++)
{
char t;
fscanf(fin,"%c",&t);
switch(t)
{
case 'F':r[i][j]=0;break;
case 'H':r[i][j]=1;break;
case 'B':r[i][j]=2;
}
}
fscanf(fin,"\n");
}
for(long i=1;i<=n;i++)
for(long j=1;j<=m;j++)
fscanf(fin,"%ld",&a[i][j]);
}
void build()
{
count=0;
for(long i=1;i<=n;i++)
for(long j=1;j<=m;j++)
{
first[f(i,j)]=0;
for(long k=0;k<8;k++)
if(i+xd[k]>=1&&i+xd[k]<=n&&j+yd[k]>=1&&j+yd[k]<=m)
{
count++;
e[count].v=f(i+xd[k],j+yd[k]);
e[count].w=a[i+xd[k]][j+yd[k]];
if(r[i][j]!=r[i+xd[k]][j+yd[k]]) e[count].w+=c[r[i+xd[k]][j+yd[k]]];
e[count].next=first[f(i,j)];
first[f(i,j)]=count;
}
}
}
void spfa()
{
long s=f(x,y),t,p;
for(long i=1;i<=f(n,m);i++)
d[i]=(i==s?a[x][y]+c[r[x][y]]:INF);
memset(inq,false,sizeof(inq));
Clear();
Push(s);inq[s]=true;
while(!Empty())
{
Pop(t);inq[t]=false;
for(p=first[t];p;p=e[p].next)
if(d[t]+e[p].w<d[e[p].v])
{
d[e[p].v]=d[t]+e[p].w;
if(!inq[e[p].v])
{
Push(e[p].v);inq[e[p].v]=true;
}
}
}
}
void output()
{
long ans=0;
for(long i=1;i<=k;i++)
{
long begin,end;
fscanf(fin,"%ld%ld",&begin,&end);
ans+=d[f(begin,end)];
}
fprintf(fout,"%ld\n",ans);
}
void close()
{
fclose(fin);fclose(fout);
}
int main()
{
input();
build();
spfa();
output();
close();
return 0;
}
posted on 2010-03-29 10:12
lee1r 阅读(1961)
评论(0) 编辑 收藏 引用 所属分类:
题目分类：图论