题解

#include <bits/stdc++.h>
#define debug freopen("in.txt","r",stdin),freopen("out.txt","w",stdout);
using namespace std;
int read ()
{
    int x = 0, w = 1;
    char ch = getchar ();
    while (ch < '0' || ch > '9')
    {
        if (ch == '-')
            w = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = x * 10 + (ch - '0');
        ch = getchar ();
    }
    return x * w;
}
void write (int x)
{
    int sta[35];
    int top = 0;
    do
    {
        sta[top++] = x % 10, x /= 10;
    } while (x);
    while (top)
        putchar (sta[--top] + 48);
}
struct edge
{
    int u, v, w;
} e[10005];
int cnt, n, m, s, dis[10005];
void add_edge (int u, int v, int w)
{
    e[++cnt].u = u;
    e[cnt].v = v;
    e[cnt].w = w;
}
bool bellman_fold (int u)
{
    memset (dis, 0x3f, sizeof (dis));
    dis[u] = 0;
    for (int i = 1; i <= n - 1; i++)
    {
        bool flag = false; 
        for (int j = 1; j <= m; j++)
        {
            if (dis[e[j].v] > dis[e[j].u] + e[j].w)
            {
                dis[e[j].v] = dis[e[j].u] + e[j].w;
                flag = true;
            }
        }
        if (!flag)
            return false; 
    }
    for (int j = 1; j <= m; j++) 
        if (dis[e[j].v] > dis[e[j].u] + e[j].w)
            return true; 
    return false;
}
void init ()
{
    n = read (), m = read (), s = read ();
    int u, v, w;
    for (int i = 1; i <= m; i++)
    {
        u = read (), v = read (), w = read ();
        add_edge (u, v, w);
    }
    if (bellman_fold (s))
        printf ("%s\n", "no solution");
    else
    {
        for (int i = 1; i <= n; i++)
            if(dis[i]==dis[0])
                printf("-1 ");
            else
                printf ("%d ", dis[i]);
    }
}
int main ()
{
    init ();
    return 0;
}