题解 D 刺客信条

很明显是一道最短路的题，可以用迪杰斯特拉算法求解。

可以把每一个点拆成入点和出点，入点向出点连点权的边。

从 S 的出点开始跑最短路，求出到 T 的入点的最短路即可。

#include<bits/stdc++.h>
#define re 
using namespace std;
inline int read(){
    re int t=0;re char v=getchar();
    while(v<'0')v=getchar();
    if(v=='S'||v=='E')return v+100;
    if(v>='A')return 100;
    while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
    return t;
}
int n,ans,m,val[32][32],head[20002],cnt;
struct edge{
    int to,next,w;
}e[300002];
inline void add(re int x,re int y,re int w){
    e[++cnt]=(edge){y,head[x],w};
    head[x]=cnt;
}
inline int pos(re int x,re int y){
    return (x-1)*m+y;
}
struct node{
    int pos,dis;
    bool operator <(const node x)const{
        return dis>x.dis;
    }
}h[50002];
priority_queue <node> q;
bool v[50005];
inline void dis(re int s){for(re int i=1;i<=2*m*n;++i)h[i].dis=1e9,h[i].pos=i;
    h[s].dis=0;
    q.push(h[s]);
    while(!q.empty()){
        while((h[q.top().pos].dis<q.top().dis)){q.pop();if(q.empty())break;
        }
        if(q.empty())break;
        node tmp=q.top();
        q.pop();
        for(re int i=head[tmp.pos];i;i=e[i].next){
            if((tmp.dis+e[i].w)<h[e[i].to].dis){
                h[e[i].to].dis=tmp.dis+e[i].w;
                q.push(h[e[i].to]);
            }
        }

    }
}
signed main(){
    n=read();m=read();
    for(re int i=1;i<=n;++i)for(re int j=1;j<=m;++j)val[i][j]=read();
    for(re int i=1;i<=n;++i){
        for(re int j=1;j<=m;++j){
            add(pos(i,j),pos(i,j)+n*m,val[i][j]);
            if(i!=1)add(pos(i,j)+n*m,pos(i-1,j),0);
            if(j!=1)add(pos(i,j)+n*m,pos(i,j-1),0);
            if(i!=n)add(pos(i,j)+n*m,pos(i+1,j),0);
            if(j!=m)add(pos(i,j)+n*m,pos(i,j+1),0);
            //printf("%d %d %d\n",i,j,val[i][j]);
        }
    }
    for(re int i=1;i<=n;++i)for(re int j=1;j<=m;++j)if(val[i][j]==100+'S')dis(pos(i,j)+n*m);
    for(re int i=1;i<=n;++i)for(re int j=1;j<=m;++j)if(val[i][j]==100+'E')printf("%d",h[pos(i,j)].dis);
}