[C++] 파티 (백준 1238번)

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

 

#include <iostream>
#include <vector>
using namespace std;

int n, m, x;
vector<vector<int>> g;
int MAX = 1000000000;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> x;
    g = vector<vector<int>>(n + 1, vector<int>(n + 1, MAX));

    for (int i = 0; i < n + 1; i++) {
        g[i][i] = 0;
    }

    for (int i = 0; i < m; i++) {
        int a, b, t;
        cin >> a >> b >> t;
        g[a][b] = t;
    }

    for (int k = 1; k < n + 1; k++) { // 경유지 k
        for (int i = 1; i < n + 1; i++) { // 출발 노드 i
            for (int j = 1; j < n + 1; j++) { // 도착 노드 j
                g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
            }
        }
    }

    int maxa = 0;
    for (int i = 1; i < n + 1; i++) {
        maxa = max(maxa, g[i][x] + g[x][i]);
    }
    cout << maxa << '\n';
}

처음에는 다익스트라로 하려고 했는데, 어차피 사람당 갔다 왔다 이렇게 2번 해야 해서 총  2*n번 해야 하니까 그냥(?) 플로이드 워셜로 풀어야겠다고 생각했다. ㅋㅋㅋ 왜 이런 생각을 ㅋㅋ 그래도 시간 초과는 안 걸렸다. 근데 질문 게시판을 보니 다익스트라로 푸는 게 정석인 것 같다. 태그도 그렇고. (AC)