티스토리 뷰

알고리즘 관련/BOJ

BOJ)1865 웜홀

JASON 자손9319 2017. 1. 5. 20:08

문제: icpc.me/1865


방향 그래프에서 시간이 거꾸로 간다는 개념이 나온다면 우선 벨만-포드를 생각해 볼 수 있다.


이때 주의 할 점은 도로는 방향이 없으므로 양 방향에 연결을 해줘야 한다. 


문제에서 질문은 출발을 하였을 때 보다 시간이 되돌아 가 있는 경우가 있는지 확인하는 것인데 


이것은 벨만-포드에서 음수 사이클 존재 여부를 확인하는 것과 동치다.


따라서 벨만-포드를 구현 한 뒤 음수 사이클 존재 여부에 따라 출력해주면 된다.


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
#include <cstdio>
#include <algorithm>
#include <vector>
#define INF 987654321
using namespace std;
int t, n, m, w, a, b, c, cycle;
int dist[505];
vector<vector<pair<intint>>> vt;
int main() {
    scanf("%d"&t);
    while (t--) {
        cycle = false;
        scanf("%d%d%d"&n, &m, &w);
        vt.clear();
        vt.resize(n + 1);
        for (int i = 0; i < m; i++) {
            scanf("%d%d%d"&a, &b, &c);
            vt[a].emplace_back(b, c);
            vt[b].emplace_back(a, c);
        }
        for (int i = 0; i < w; i++) {
            scanf("%d%d%d"&a, &b, &c);
            vt[a].emplace_back(b, -c);
        }
        for (int i = 2; i <= n; i++)
            dist[i] = INF;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                for (auto k : vt[j]) {
                    int there = k.first;
                    int d = k.second;
                    if (dist[j] != INF && (dist[there]>dist[j] + d)) {
                        dist[there] = dist[j] + d;
                        if (i == n)cycle = true;
                    }
                }
            }
        }
        if (cycle)
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)12843 복수전공  (0) 2017.01.05
BOJ)12841 정보대 등산  (0) 2017.01.05
BOJ)1865 웜홀  (0) 2017.01.05
BOJ)11999 Milk Pails  (2) 2017.01.05
BOJ)10775 공항  (0) 2017.01.04
BOJ)12845 모두의 마블  (0) 2017.01.03
댓글
댓글쓰기 폼