[Jungol] 정올 2223 블랙홀

출처: http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1484&sca=9040

Approach

벨만-포드 (Bellman-Ford) 알고리즘을 이용할 수 있다.

벨만-포드 (Bellman-Ford)

---

#include <stdio.h>
const int LM = 505;
int N, M, B, dist[LM];
struct Data {
    int s, e, t;
}A[LM * 12];

int acnt;
void input() {
    scanf("%d %d %d", &N, &M, &B);
    int i, s, e, t;
    acnt = 0;
    for (i = 0; i < M; ++i) {
        scanf("%d %d %d", &s, &e, &t);
        A[acnt++] = { s, e, t };
        A[acnt++] = { e, s, t };
    }
    for (i = 0; i < B; ++i) {
        scanf("%d %d %d", &s, &e, &t);
        A[acnt++] = { s, e, -t };
    }
}

int BellmanFord() {
    int i, j, flag;
    for (i = 0; i <= N; ++i) {
        dist[i] = 0;
    }
    for (i = 1; i <= N; ++i) {
        flag = 0;
        for (j = 0; j < acnt; ++j) {
            if (dist[A[j].e] > dist[A[j].s] + A[j].t) {
                dist[A[j].e] = dist[A[j].s] + A[j].t;
                flag = 1;
            }
        }
    }
    return flag;
}

int main() {
    // freopen("input.txt", "r", stdin);
    int tc;
    scanf("%d", &tc);
    while (tc--) {
        input();
        puts(BellmanFord() ? "YES" : "NO");
    }
    return 0;
}