@[ZYC_MUSTA_1024](/user/794430) 最短路吧
by ilibilib @ 2024-04-28 21:35:11
@[ZYC_MUSTA_1024](/user/794430)
AC https://www.luogu.com.cn/record/157372958
```
#include<bits/stdc++.h>
#define N 1000010
using namespace std;
struct qxx{int nx,to,w;}tu[N<<1];int hd[N],bs=0;
int dis[N],n,m;
struct Q{int d,w;};
bool operator <(const Q &a,const Q &b){return a.w>b.w;};
priority_queue<Q>q;
void djst(int s)
{
memset(dis,127,sizeof(dis));
q.push({s,0});dis[s]=0;Q nw;
while(!q.empty())
{
Q nw=q.top();q.pop();
if(nw.w>dis[nw.d]) continue;
for(int i=hd[nw.d];i;i=tu[i].nx)
if(dis[tu[i].to]>nw.w+tu[i].w)
{
dis[tu[i].to]=nw.w+tu[i].w;
q.push({tu[i].to,dis[tu[i].to]});
}
}
}
void add(int x,int y,int z){tu[++bs]={hd[x],y,z};hd[x]=bs;}
#define p(x,y) ((((x)-1)*n+(y)))
int g[1010][1010];
signed main()
{
int n,a,b,c,d,x;cin>>n>>a>>b>>c>>d;
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
{
cin>>g[i][j];
if(i!=1) add(p(i-1,j),p(i,j),g[i][j]);
if(i!=n) add(p(i+1,j),p(i,j),g[i][j]);
if(j!=1) add(p(i,j-1),p(i,j),g[i][j]);
if(j!=n) add(p(i,j+1),p(i,j),g[i][j]);
}
djst(p(a,b));
cout<<dis[p(c,d)]+g[a][b];
}
by ilibilib @ 2024-04-28 21:49:21
十分感谢！
by ZYC_MUSTA_1024 @ 2024-04-29 07:34:55