【题解】bellman-fold可以解决

/*
    @filename:单源最短路径2.cpp
    @author: sww
    @date: 2023-03-08 13:17:03  星期三
    @version: V1.0.0
*/
#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++) // 如果进行第n次循环
        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 ()
{
    /*
    4 6 1
    1 2 2
    2 3 2
    2 4 1
    1 3 5
    3 4 3
    1 4 4
    */
    // debug;
    init ();
    return 0;
}