飞飞国是一个传说中的国度，国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵，每个格子代表一个街区。然而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第i行第j列的弹射装置有Aij的费用和Bij的弹射能力。并规定有相邻边的格子间距离是1。那么，任何飞飞侠都只需要在(i,j)支付Aij的费用就可以任意选择弹到距离不超过Bij的位置了。如下图 
（从红色街区交费以后可以跳到周围的任意蓝色街区。） 现在的问题很简单。有三个飞飞侠，分别叫做X，Y，Z。现在它们决定聚在一起玩，于是想往其中一人的位置集合。告诉你3个飞飞侠的坐标，求往哪里集合大家需要花的费用总和最低。
输入的第一行包含两个整数N和M，分别表示行数和列数。接下来是2个N×M的自然数矩阵，为Aij和Bij 最后一行六个数，分别代表X，Y，Z所在地的行号和列号。
第一行输出一个字符X、Y或者Z。表示最优集合地点。第二行输出一个整数，表示最小费用。如果无法集合，只输出一行NO
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 #define inf 1000000000 5 using namespace std; 6 char ans;int mn=inf; 7 int fx[5]={0,0,1,-1,0},fy[5]={1,-1,0,0,0}; 8 int a1,a2,b1,b2,c1,c2; 9 int n,m,mx; 10 int x1,y1,x2,y2,x3,y3; 11 int a[155][155],b[155][155]; 12 int d[155][155][305]; 13 bool vis[155][155][305]; 14 struct node{int s,x,y,w;}; 15 bool cmp(node a,node b) {return a.w<b.w;} 16 bool operator>(node a,node b) 17 { 18 return a.w>b.w; 19 } 20 void dij(int x,int y){ 21 priority_queue<node,vector<node>,greater<node> > q; 22 for(int i=1;i<=n;i++) 23 for(int j=1;j<=m;j++) 24 for(int k=0;k<=mx;k++){ 25 vis[i][j][k]=0; 26 d[i][j][k]=inf; 27 } 28 vis[x][y][0]=1;d[x][y][b[x][y]]=a[x][y]; 29 q.push((node){b[x][y],x,y,a[x][y]});//层数，坐标xy，花费 30 while(!q.empty()&&(!vis[x1][y1][0]||!vis[x2][y2][0]||!vis[x3][y3][0])){ 31 int x=q.top().x,y=q.top().y,s=q.top().s;q.pop(); 32 if(vis[x][y][s]) continue;vis[x][y][s]=1; 33 if(s>0){ 34 for (int i=0;i<5;i++){ 35 int xx=x+fx[i],yy=y+fy[i]; 36 if(xx>n||xx<1||yy>m||yy<1||vis[xx][yy][s-1]) continue; 37 if(d[x][y][s]<d[xx][yy][s-1]){ 38 d[xx][yy][s-1]=d[x][y][s]; 39 q.push((node){s-1,xx,yy,d[xx][yy][s-1]}); 40 } 41 } 42 } 43 else{ 44 int t=b[x][y]; 45 if(d[x][y][t]>d[x][y][0]+a[x][y]){ 46 d[x][y][t]=d[x][y][0]+a[x][y]; 47 q.push((node){t,x,y,d[x][y][t]}); 48 } 49 } 50 51 } 52 while(!q.empty())q.pop(); 53 } 54 55 int main(){ 56 scanf("%d%d",&n,&m);mx=n+m-2; 57 for (int i=1;i<=n;i++) 58 for (int j=1;j<=m;j++) 59 scanf("%d",&b[i][j]),b[i][j]=min(max(mx-i-j,i+j-2),b[i][j]); 60 for (int i=1;i<=n;i++) 61 for (int j=1;j<=m;j++) scanf("%d",&a[i][j]); 62 63 scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3); 64 dij(x1,y1);a1=d[x2][y2][0],a2=d[x3][y3][0]; 65 dij(x2,y2);b1=d[x1][y1][0],b2=d[x3][y3][0]; 66 dij(x3,y3);c1=d[x1][y1][0],c2=d[x2][y2][0]; 67 if(b1+c1<mn) ans=‘X‘,mn=b1+c1; 68 if(a1+c2<mn) ans=‘Y‘,mn=a1+c2; 69 if(a2+b2<mn) ans=‘Z‘,mn=a2+b2; 70 if(mn==inf) {printf("NO\n");return 0;} 71 printf("%c\n",ans); 72 printf("%d",mn); 73 }
原文：http://www.cnblogs.com/wuminyan/p/5194200.html