글 읽기 - 이 문제 플로이드 워셜로 풀 수 없나요?

playsworld16 3년 전 0

1. 플로이드 워셜로 모든 정점 쌍 사이의 최단거리를 구한다

2. 웜홀을 a, b, t로 받았을 때

2-1. b에서 a로 가는 최단거리가 t보다 작으면 YES

2-2. 그런 경우가 없으면 NO

3. 반복

의 논리로 했습니다만 30% 언저리에서 틀렸습니다가 뜨네요.

논리에 오류가 있는지, 구현에 오류가 있는지 잘 모르겠습니다.

아래는 제 코드입니다.

#include <bits/stdc++.h>
using namespace std;

#define INF 1000000000


int path[501][501];

int main() {

    int t, n, m, w, n1, n2, n3;
    vector<tuple<int, int, int>> worm;
    cin >> t;
    while (t--) {
        cin >> n >> m >> w;

        worm.clear();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) path[i][j] = 0;
                else path[i][j] = INF;
            }
        }

        
        while (m--) {
            cin >> n1 >> n2 >> n3;
            path[n1][n2] = min(path[n1][n2], n3);
            path[n2][n1] = min(path[n2][n1], n3);
        }

        for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) for (int k = 1; k <= n; k++) {
            path[j][k] = min(path[j][k], path[j][i] + path[i][k]);
        }



        for (int i = 1; i <= w; i++) {
            cin >> n1 >> n2 >> n3;
            worm.push_back({ n1, n2, n3 });
        }

        bool ok = false;
        for (auto i : worm) {
            tie(n1, n2, n3) = i;
            if (path[n2][n1] < n3) {
                ok = true;
                break;
            }
        }

        if (ok) cout << "YES\n";
        else cout << "NO\n";
    }
}