문제

문제 링크

어떻게 접근할 것인가

  • 이 문제는 모든 친구들의 왕복 최단 거리를 알아야한다.
  • 그래서 플로이드 와샬 알고리즘을 이용해서 문제를 풀었다.

코드

#include <cstdio>

using namespace std;

int n, m, x, w, v1, v2, M, d[1001][1001];

char buf[1 << 17];

inline char read() {
    static int idx = 1 << 17;
    if (idx == 1 << 17) {
        fread(buf, 1, 1 << 17, stdin);
        idx = 0;
    }
    return buf[idx++];
}
inline int readInt() {
    int sum = 0;
    bool flg = 1;
    char now = read();

    while (now == 10 || now == 32) now = read();
    if (now == '-') flg = 0, now = read();
    while (now >= 48 && now <= 57) {
        sum = sum * 10 + now - 48;
        now = read();
    }

    return flg ? sum : -sum;
}

int main(){
    n = readInt(), m = readInt(), x = readInt();
    for(int i = 1; i < n + 1; i++){
        for(int j = 1; j < n + 1; j++)d[i][j] = 1000000;
        d[i][i] = 0;
    }
    for(int i = 0; i < m; i++){
        v1 = readInt(), v2 = readInt(), w = readInt();
        d[v1][v2] = w;
    }
    for(int k = 1; k < n + 1; k++){
        for(int i = 1; i < n + 1; i++){
            for(int j = 1; j < n + 1; j++){
                if(d[i][j] > d[i][k] + d[k][j])d[i][j] = d[i][k] + d[k][j];
            }
        }
    }
    for(int i = 1; i < n + 1; i++){
        if(M < d[i][x] + d[x][i])M = d[i][x] + d[x][i];
    }
    printf("%d", M);
}

느낀점

  • 생각보다 다익스트라를 사용한 최적 코드들 보다 시간이 많이 걸렸다.
  • 찾아보니 edge가 촘촘하지 않은 상황에서는 다익스트라를 사용하는 것이 훨씬 효율적이라고 한다.
  • 다음번에는 다익스트라를 더 애용해야겠다.