[백준 / BOJ] C++ 1865 웜홀

1865번: 웜홀

 

문제

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

1865번: 웜홀

 

 

풀이

어느 시작점에서 다시 시작 지점으로 돌아올 때 시간이 되돌아갈 수 있는지 여부를 구하는 문제다. 벨만 포드 알고리즘을 사용해 풀 수 있다.

도로는 양방향이지만 웜홀은 단방향임을 주의해야 한다.

 

처음엔 dist[1] < 0 이면 YES를 출력하도록 했다. 그러나 2%틀을 받고 모든 정점에서 다 해보는 코드를 짰는데 90% 언저리에서 시간초과가 났다. 결국 벨만 포드의 특성상 어느 정점에서 시작하던지 결과는 같게 나올 것이다. 그러므로 시작 정점이 어디든 어느 한 구간에서 음의 사이클이 생긴다면, 그중 한 정점이 우리가 원하는 한 정점이기 때문에 YES가 된다.

 

그리고 dist[j] != INF 라는 조건이 벨만-포드 알고리즘 안에 있었는데 이걸 제거하니 맞았다. 이유를 사실 잘 모르겠어서 누군가 아는 사람이 나타나 줬으면 좋겠다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    int N, M, W;
    vector<pair<int, int>> graph[501];
    vector<int> dist(501, INF);
    bool minusCycle = false;
    cin >> N >> M >> W;
    while (M--) {
      int s, e, t;
      cin >> s >> e >> t;
      graph[s].push_back({e, t});
      graph[e].push_back({s, t});
    }
    while (W--) {
      int s, e, t;
      cin >> s >> e >> t;
      graph[s].push_back({e, -t});
    }
    dist[1] = 0;
    for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++)
        for (auto &p : graph[j]) {
          int next = p.first, d = p.second;
          if (dist[next] > dist[j] + d) {
            dist[next] = dist[j] + d;
            if (i == N)
              minusCycle = true;
          }
        }
    cout << (minusCycle ? "YES\n" : "NO\n");
  }
  return 0;
}