//SPFA
//该代码是可以判断负环的SPFA，且采用vector存边

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <deque>
#include <functional>
#include <climits>

#define quickio ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
#define endl "\n"

using namespace std;
typedef long long ll;

const int N = 1e5 + 5;

struct edge
{
    int v;
    int w;
};
int vis[N];//标记是否在队内，所有pop后要置为0，和Dij不一样！！！！！！！！，Dij是标记该点访问过，不再访问
int ans[N];
int countt[N];//经过每个点的次数，如果有一个点的次数 >= n，则有负环

vector<edge>e[N];

int n, m, s;

bool SPFA(int s)
{
    queue<int>que;
    memset(ans, 0x3f, sizeof(ans));
    ans[s] = 0;
    que.push(s);
    vis[s] = 1;

    while (!que.empty())
    {
        int dian = que.front();
        que.pop();
        vis[dian] = 0;/*出队是0，注意！！！！！！！！！！，vis是表示是否在队内的*/
        countt[dian]++;

        if (countt[dian] >= n)
            return true;//返回true表示有负环

        for (auto ed : e[dian])
        {
            int v = ed.v;
            int w = ed.w;

            if (ans[v] > ans[dian] + w)
            {
                ans[v] = ans[dian] + w;
                countt[v] = countt[dian] + 1;
                if (countt[v] >= n)
                    return true;//返回true表示有负环

                if (vis[v] == 0)
                {
                    vis[v] = 1;
                    que.push(v);
                }
            }
        }
    }
    return false;
}

int main()
{
    cin >> n >> m >> s;
    int u, v, w;
    for (int i = 0; i < m; i++)
    {
        cin >> u >> v >> w;
        e[u].push_back({ v, w });
    }
    SPFA(s);
    for (int i = 1; i <= n; i++)
        cout << ans[i] << " ";
    return 0;
}

弱化版90分，标准版一个过不了，怎么改，这个代码样例没过，但是交上去有90分