문제

문제 링크

어떻게 접근할 것인가

  • 이 문제는 negative edge가 존재하는데 이것이 negative cycle을 발생시키는지 보는 문제이다.
  • 벨만포드에서 negative cycle 체크하는 방법을 이용하면 된다.

유의점 및 힌트

  • 처음에 주어지는 M개의 도로의 정보는 양방향이고 뒤의 웜홀 정보는 단방향이다.(이것 때문에 엄청 헤맸다…)
  • 이 문제의 포인트는 시작점은 아무렇게나 해도 된다는 것이다.
  • 그 이유는 어차피 다시 검토할 때 edge를 모두 돌게 되는데 이것은 시작 점도 다른 점들과 동일하게 검토 대상이 되기 때문이다.

코드

#include <cstdio>
#define INF 987654321

using namespace std;

int main(){
    int tc, n, m, w, t, e[6000][3], dist[501], before[501];
    scanf("%d", &tc);
    while(tc--){
        int yes = 0;
        scanf("%d %d %d", &n, &m, &w);
        for(int i = 0; i < m; i++) scanf("%d %d %d", &e[i][0], &e[i][1], &e[i][2]);
        for(int i = m; i < 2*m; i++) e[i][0] = e[i-m][1], e[i][1] = e[i-m][0], e[i][2] = e[i-m][2];
        for(int i = 2*m; i < 2*m + w; i++){
            scanf("%d %d %d", &e[i][0], &e[i][1], &t);
            e[i][2] = -t;
        }
        for(int i = 1; i < n + 1; i++) dist[i] = INF;
        dist[1] = 0;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < (2*m + w); j++){
                if(dist[e[j][0]] == INF) continue;
                if(dist[e[j][1]] > dist[e[j][0]] + e[j][2]) dist[e[j][1]] = dist[e[j][0]] + e[j][2];
            }
        }
        //확인하기 전에 모든 경로 저장하기
        for(int i = 1; i < n + 1; i++) before[i] = dist[i];
        for(int i = 0; i < (2 * m + w); i++){
            if(dist[e[i][0]] == INF) continue;
            if(dist[e[i][1]] > dist[e[i][0]] + e[i][2]) dist[e[i][1]] = dist[e[i][0]] + e[i][2];
        }
        for(int i = 1; i < n + 1; i++){
            if(dist[i] != before[i]) {
                yes = 1;
                break;
            }
        }
        if(yes) printf("YES\n");
        else printf("NO\n");
    }
}

느낀점

  • 벨만 포드를 머리로 구현하는데는 조금 아직 어려운 것 같다.
  • 좀더 비슷한 유형을 풀어보며 적응해보자!