SPFA에서 음수 사이클을 확인하는 방법

이러한 사실을 이용하여 BOJ)11657 타임머신 문제를 spfa로 풀 수 있다.

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#define INF 987654321
using namespace std;
int n, m, a, b, c;
vector<vector<pair<int,int>>> vt;
vector<int> v, cycle, dist;
int main() {
    scanf("%d%d", &n, &m);
    vt.resize(n + 1);
    for (int i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        vt[a].push_back({ b,c });
    }
    v.assign(n + 1, 0);
    cycle.assign(n + 1, 0);
    dist.assign(n + 1, INF);
    queue<int> qu;
    qu.push(1);
    v[1] = 1;
    dist[1] = 0;
    cycle[1]++;
    while (qu.size()) {
        int here = qu.front();
        qu.pop();
        v[here] = 0;
        for (auto next : vt[here]) {
            if (dist[next.first] > dist[here] + next.second) {
                dist[next.first] = dist[here] + next.second;          
                if (cycle[next.first] == n) {
                    puts("-1");
                    return 0;
                }
                if (!v[next.first]) {
                    cycle[next.first]++;
                    v[next.first] = 1;
                    qu.push(next.first);
                }
            }
        }
    }
    for (int i = 2; i <= n; i++) {
        if (dist[i] == INF)puts("-1");
        else printf("%d\n", dist[i]);
    }
    return 0;
}