2018.11.05 bzoj2143: 飞飞侠(最短路)
程序员文章站
2022-03-03 11:34:18
...
传送门
最短路好题。
考虑对每个二维坐标建立一个高度属性。
这样每次如果在点只能选择花费跳向,然后如果当前状态的高度不是就可以花费的代价选择让高度下降一个,同时向周围四格走一步或者原地不动。
然后跑三次最短路就可以了。
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=210,M=420;
const ll inf=1e18;
int n,m,K,a[N][N],X1,X2,X3,Y1,Y2,Y3,dx[5]={0,0,1,-1,0},dy[5]={-1,1,0,0,0};
ll dis[N][N][M],len=inf,b[N][N],ltmp,W[3]={0};
bool vis[N][N][M];
string ans="NO";
inline int read(){
int ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
struct Node{
int x,y,h;
ll val;
friend inline bool operator<(const Node&a,const Node&b){return a.val==b.val?a.h>b.h:a.val>b.val;}
};
priority_queue<Node>q;
inline void dijkstra(int sx,int sy,int tx1,int ty1,int tx2,int ty2){
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)for(int k=0;k<=K;++k)dis[i][j][k]=inf,vis[i][j][k]=0;
while(!q.empty())q.pop();
q.push((Node){sx,sy,a[sx][sy],dis[sx][sy][a[sx][sy]]=b[sx][sy]});
while(!q.empty()){
Node p=q.top();
q.pop();
if(vis[X1][Y1][0]&&vis[X2][Y2][0]&&vis[X3][Y3][0])return;
if(vis[p.x][p.y][p.h])continue;
vis[p.x][p.y][p.h]=1;
if(p.h){
for(int i=0,nx,ny,nh=p.h-1;i<5;++i){
nx=p.x+dx[i],ny=p.y+dy[i];
if(!nx||!ny||nx>n||ny>m||vis[nx][ny][nh])continue;
if(dis[nx][ny][nh]>p.val){
dis[nx][ny][nh]=p.val;
q.push((Node){nx,ny,nh,p.val});
}
}
}
else{
if(dis[p.x][p.y][a[p.x][p.y]]>p.val+b[p.x][p.y]){
dis[p.x][p.y][a[p.x][p.y]]=p.val+b[p.x][p.y];
q.push((Node){p.x,p.y,a[p.x][p.y],dis[p.x][p.y][a[p.x][p.y]]});
}
}
}
}
int main(){
n=read(),m=read(),K=n+m-2;
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)a[i][j]=min(read(),K);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)b[i][j]=read();
X1=read(),Y1=read(),X2=read(),Y2=read(),X3=read(),Y3=read();
dijkstra(X1,Y1,X2,Y2,X3,Y3);
W[1]+=dis[X2][Y2][0],W[2]+=dis[X3][Y3][0];
dijkstra(X2,Y2,X1,Y1,X3,Y3);
W[2]+=dis[X3][Y3][0],W[0]+=dis[X1][Y1][0];
dijkstra(X3,Y3,X1,Y1,X2,Y2);
W[0]+=dis[X1][Y1][0],W[1]+=dis[X2][Y2][0];
if(len>W[0])ans="X",len=W[0];
if(len>W[1])ans="Y",len=W[1];
if(len>W[2])ans="Z",len=W[2];
cout<<ans;
if(len==inf)return 0;
cout<<'\n'<<len;
return 0;
}