bzoj2143: 飞飞侠（最短路）
2143: 飞飞侠
Time Limit: 50 Sec
Memory Limit: 259 MB
Description
飞飞国是一个传说中的国度，国家的居民叫做飞飞侠。飞飞国是一个N×M的矩形方阵，每个格子代表一个街区。然
而飞飞国是没有交通工具的。飞飞侠完全靠地面的弹射装置来移动。每个街区都装有弹射装置。使用弹射装置是需
要支付一定费用的。而且每个弹射装置都有自己的弹射能力。我们设第i行第j列的弹射装置有Aij的费用和Bij的弹
射能力。并规定有相邻边的格子间距离是1。那么，任何飞飞侠都只需要在(i,j)支付Aij的费用就可以任意选择弹
到距离不超过Bij的位置了。如下图
（从红色街区交费以后可以跳到周围的任意蓝色街区。）现在的问题很简单。有三个飞飞侠，分别叫做X，Y，Z。
现在它们决定聚在一起玩，于是想往其中一人的位置集合。告诉你3个飞飞侠的坐标，求往哪里集合大家需要花的
费用总和最低。
Input
输入的第一行包含两个整数N和M，分别表示行数和列数。
接下来是2个N×M的自然数矩阵，为Aij和Bij
最后一行六个数，分别代表X，Y，Z所在地的行号和列号。
Output
第一行输出一个字符X、Y或者Z。表示最优集合地点。
第二行输出一个整数，表示最小费用。如果无法集合，只输出一行NO
Sample Input
4 4
0 0 0 0
1 2 2 0
0 2 2 1
0 0 0 0
5 5 5 5
5 5 5 5
5 5 5 5
5 5 5 5
2 1 3 4 2 2
Sample Output
Z
15
解：
黄学长的代码似乎wa了，有两个人在同一个点上时就凉了。
但是想法是对的，我们点比较少，所以拆点。我们想到花费其实是给自己加油，然后花一点油可以走到旁边。我们拆点，(i,j,k)表示到i，j坐标还剩k点油的最短路。然后每种状态就只会有5种连边。跑三遍最短路即可。
细节上为什么(x,y,0)被打标记就结束？其实好像只要(x,y,_)中有一个打上标记就可以结束，因为dj最短路一定近的点先打标记，所以先出堆的一定是最短的。当时没有想清楚，所以写的有点傻。还有就是一定要退出，不然特别慢，根本不像一个复杂度。被dj制裁了，好久没写过了。
code：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
struct lxy{
int x,y,k;
long long dis;
bool operator < (const lxy &QAQ)const{
return dis>QAQ.dis;
}
}yyy;
int n,m;
int a[155][155];
int b[155][155];
long long dis[155][155][305],ans=0x3f3f3f3f3f3f3f3f,len[5][5];
int g[155][155];
bool vis[155][155][305];
int x1,y1,x2,y2,x3,y3,fg;
priority_queue <lxy> d;
void addans()
{
for(int i=0;i<=300;i++)
len[fg][1]=min(len[fg][1],dis[x1][y1][i]);
for(int i=0;i<=300;i++)
len[fg][2]=min(len[fg][2],dis[x2][y2][i]);
for(int i=0;i<=300;i++)
len[fg][3]=min(len[fg][3],dis[x3][y3][i]);
}
void spfa(int x,int y)
{
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[x][y][0]=0;yyy.x=x;yyy.y=y;yyy.k=0;yyy.dis=0;d.push(yyy);
while(!d.empty()&&(!vis[x1][y1][0]||!vis[x2][y2][0]||!vis[x3][y3][0])){
lxy now=d.top();
vis[now.x][now.y][now.k]=1;d.pop();
if(dis[now.x][now.y][g[now.x][now.y]]>dis[now.x][now.y][now.k]+a[now.x][now.y]){
dis[now.x][now.y][g[now.x][now.y]]=dis[now.x][now.y][now.k]+a[now.x][now.y];
yyy.x=now.x;yyy.y=now.y;yyy.k=g[now.x][now.y];yyy.dis=dis[now.x][now.y][g[now.x][now.y]];d.push(yyy);
}
if(now.x<n&&now.k!=0){
if(dis[now.x+1][now.y][now.k-1]>dis[now.x][now.y][now.k]){
dis[now.x+1][now.y][now.k-1]=dis[now.x][now.y][now.k];
yyy.x=now.x+1;yyy.y=now.y;yyy.k=now.k-1;yyy.dis=dis[now.x+1][now.y][now.k-1];d.push(yyy);
}
}
if(now.y<m&&now.k!=0){
if(dis[now.x][now.y+1][now.k-1]>dis[now.x][now.y][now.k]){
dis[now.x][now.y+1][now.k-1]=dis[now.x][now.y][now.k];
yyy.x=now.x;yyy.y=now.y+1;yyy.k=now.k-1;yyy.dis=dis[now.x][now.y+1][now.k-1];d.push(yyy);
}
}
if(now.x>1&&now.k!=0){
if(dis[now.x-1][now.y][now.k-1]>dis[now.x][now.y][now.k]){
dis[now.x-1][now.y][now.k-1]=dis[now.x][now.y][now.k];
yyy.x=now.x-1;yyy.y=now.y;yyy.k=now.k-1;yyy.dis=dis[now.x-1][now.y][now.k-1];d.push(yyy);
}
}
if(now.y>1&&now.k!=0){
if(dis[now.x][now.y-1][now.k-1]>dis[now.x][now.y][now.k]){
dis[now.x][now.y-1][now.k-1]=dis[now.x][now.y][now.k];
yyy.x=now.x;yyy.y=now.y-1;yyy.k=now.k-1;yyy.dis=dis[now.x][now.y-1][now.k-1];d.push(yyy);
}
}
while(!d.empty()&&vis[d.top().x][d.top().y][d.top().k]==1) d.pop();
}
while(!d.empty())d.pop();
addans();
}
int main()
{
memset(len,0x3f,sizeof(len));
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&b[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
g[i][j]=min(b[i][j],max(i-1,n-i)+max(j-1,m-j));
scanf("%d%d%d%d%d%d",&x1,&y1,&x2,&y2,&x3,&y3);
fg=1;spfa(x1,y1);
fg=2;spfa(x2,y2);
fg=3;spfa(x3,y3);
fg=0;
for(int i=1;i<=3;i++)
{
long long t=0;
for(int j=1;j<=3;j++)
t+=len[j][i];
if(t<ans) ans=t,fg=i;
}
if(fg==0) printf("NO");
if(fg==1) printf("X\n%lld",ans);
if(fg==2) printf("Y\n%lld",ans);
if(fg==3) printf("Z\n%lld",ans);
}