BOJ 1956: 운동

https://www.acmicpc.net/problem/1956

  • 2월동안 187문제 풀기(지난달 누적 87개) (75/187)
  • 11657 타임머신 도 같은 벨만포드임 생략
  • 음수 사이클 찾기, 벨만포드로 찾으면 됨.
  • 도로는 양방향이라는 함정이 도사리고 있음
  • 그리고 여러 Component로 이뤄진 경우를 대비해서, INF로 유지되는 도로를 다시 시작점으로 만들고 벨만포드를 돌려야함
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
#include <bits/stdc++.h>
using namespace std;

struct Edge {
  int u, v, dist;
};

int main() {
  int TC, N, M, W, A,B,C;
  scanf("%d", &TC);
  while (TC--) {
    scanf("%d %d %d", &N, &M, &W);
    vector<Edge> edges;
    for(int i = 0; i < M; i++) {
      scanf("%d %d %d", &A, &B, &C);
      edges.push_back({A,B,C})략략
      edges.push_back({B,A,C});
    }
    for(int i = 0; i < W; i++) {
      scanf("%d %d %d", &A, &B, &C);
      edges.push_back({A,B,-C});
    }

    const int INF = 1e9;
    bool neg = false;
    vector<int> dist(N+1, INF);
    while(1) {
      int i;
      for(i = 1; i <= N; i++)
        if(dist[i] == INF) {
          dist[i] = 0;
          break;
        }
      if(i == N+1) break;

      for(int i = 0; i < N; i++)
        for(auto& e: edges)
          if(dist[e.v] != INF && dist[e.u] > dist[e.v] + e.dist)
            dist[e.u] = dist[e.v] + e.dist;

      for(auto& e: edges)
        if(dist[e.v] != INF && dist[e.u] > dist[e.v] + e.dist)
          neg = true;
    }

    printf(neg ? "YES\n" : "NO\n");
  }
}