SPFA求助
查看原帖
SPFA求助
532828
huyiyang楼主2022/11/28 22:03

为什么我的SPFASPFA了???

#include <bits/stdc++.h>
using namespace std;
#define int long long
struct P{
    int n,w;
};
int n,m,s,least[11111],u,v,w,las,b[11111];
vector<P>nt[11111];
queue<int>q;
signed main()
{
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)least[i]=INT_MAX;
    while(m--){
        cin>>u>>v>>w;
        nt[u].push_back({v,w});
    }
    least[s]=0;
    b[s]=1;
    q.push(s);
    while(!q.empty()){
        las=q.front();
        b[las]=0;
        for(auto j:nt[las]){
            if(!b[j.n]){
                b[j.n]=1;
                q.push(j.n);
            }
            if(least[j.n]>least[las]+j.w)
                least[j.n]=least[las]+j.w;
        }
        q.pop();
    }
    for(int i=1;i<=n;i++)cout<<least[i]<<' ';
    return 0;
}
2022/11/28 22:03
加载中...