欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

2018.11.05 bzoj2143: 飞飞侠(最短路)

程序员文章站 2022-03-03 11:34:18
...

传送门
最短路好题。


考虑对每个二维坐标建立一个高度属性。
这样每次如果在点(i,j,0)(i,j,0)只能选择花费bi,jb_{i,j}跳向(i,j,ai,j)(i,j,a_{i,j}),然后如果当前状态的高度不是00就可以花费00的代价选择让高度下降一个,同时向周围四格走一步或者原地不动。
然后跑三次最短路就可以了。
代码:

#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;
}

相关标签: 图论