SPFA优化
2024-11-02 20:03:00
发布于：上海
3阅读
0回复
0点赞
#include<bits/stdc++.h>
using namespace std;
int a[5555][5555];
int n , m , w , x , y , z , s , t;
int d[2505],vis[2505];
int main(){
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i = 1;i <= n;i++){
vis[i]=0,d[i] = 1e9;
}
for(int i = 1;i <= n;i++){
for(int j = 1;j <= n;j++)
{
a[i][j]=1e9;
}
}
for(int i = 1;i <= m;i++){
int ax,bx,cx;
cin>>ax>>bx>>cx;
a[ax][bx]=cx;
}
d[s] = 0;
vis[s]=1;
queue<int> q;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=0;
for(int i=1;i<=n;i++)
{
if(d[i]>d[u]+a[u][i])
{
d[i]=d[u]+a[u][i];
if(!vis[i])
{
vis[i]=1;
q.push(i);
}
}
}
}
cout<<d[t];
return 0;
}
这里空空如也
有帮助，赞一个