[백준] 1238 - 파티

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

1238번: 파티

 

간단한 플로이드-워셜 알고리즘 문제

https://ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

3중첩 for-loop를 이용하여 최단 경로를 제공하는 경유지를 탐색한다.

 

<C++ 코드>

#include <cstdio>
#include <algorithm>
using namespace std;
 
int dist[1001][1001];
 
int main(){
    int n, m, x;
    scanf("%d %d %d", &n, &m, &x);
 
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            dist[i][j] = 1000000;
        }
        dist[i][i] = 0;
    }
 
    for(int i=0; i<m; i++){
        int s, e, v;
        scanf("%d %d %d", &s, &e, &v);
        dist[s][e] = min(dist[s][e], v);
    }
 
    for(int k=1; k<=n; k++){
        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++){
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
 
    int re = 0;
    for(int i=1; i<=n; i++){
        re = max(re, dist[i][x] + dist[x][i]);
    }
    printf("%d", re);
 
    return 0;
}