본문 바로가기

일상/개인

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



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


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#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 + 10);
    cycle.assign(n + 10);
    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;
}

cs


'일상 > 개인' 카테고리의 다른 글

스터디를 위한 링크드 리스트  (0) 2017.04.25