A551.单源最短路径2 铃铛人题解

#include<bits/stdc++.h>
//pretreatment
#define N 1005
#define ll long long
#define ull unsigned long long
#define endl '\n'
using namespace std;
// variables setting
int n,m,s;
int dis[1010],u,v,w,cnt;
const int INF=0x3f3f3f3f;
struct edge
{
    int u,v,w;
}e[N];
// functions defining
void add_edge(int u,int v,int w)
{
    e[++cnt]=edge{u,v,w};
}
bool bellmen_ford()
{
    memset(dis,INF,sizeof(dis));
    dis[s]=0;
    for(int i=1;i<n;i++)
    {
        bool flag=true;
        for(int j=1;j<=m;j++)
        {
            if(dis[e[j].u]!=INF&&dis[e[j].v]>dis[e[j].u]+e[j].w)
                {dis[e[j].v]=dis[e[j].u]+e[j].w;flag=false;}
        }
        if(flag)return false;
    }
    for(int j=1;j<=m;j++)
    {
        if(dis[e[j].v]!=INF&&dis[e[j].v]>dis[e[j].u]+e[j].w)
        {
            dis[e[j].v]=dis[e[j].u]+e[j].w;return true;
        }
    }
}
// the program subject
void program()
{
    cin>>n>>m>>s;
    for(int i=1;i<=m;i++)
    {
        cin>>u>>v>>w;
        add_edge(u,v,w);
    }
    if(bellmen_ford())cout<<"no solution"<<endl;
    else
    {
        for(int i=1;i<=n;i++)
        {
            if(dis[i]==INF)cout<<-1<<" ";
            else cout<<dis[i]<<" ";
        }
    }
}
// the main function
int main()
{
    program();
    return 0;
}