[백준oj] 1238번 파티

www.acmicpc.net/problem/1238

1238번: 파티

---

 

이 문제는 모든마을에서 모든마을까지의 최단거리를 구하는 Floyd-warshall알고리즘을 사용하여 풀면된다.

다익스트라를 돌린뒤, x마을을 제외한 전체마을을 탐색하며 i->x + x->i값의 최댓값을 구해주면 된다.

 

#include<iostream>
#include<algorithm>
#define MAX 987654321
using namespace std;
int n, m, x;
int arr[1001][1001];

int main() {
	cin >> n >> m>>x;
    //초반 초기화
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) arr[i][j] = 0;
			else arr[i][j] = MAX;
		}
	}
    
    //도로 입력
	for (int i = 0; i < m; i++) {
		int st, en, v;
		cin >> st >> en >> v;
		arr[st][en] = v;
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
            	//k마을을 거쳐가는 길이 더 빠르면 업데이트
				if (arr[i][j] > arr[i][k] + arr[k][j]) {
					arr[i][j] = arr[i][k] + arr[k][j];
				}
			}
		}
	}
	int mx = -1;
	
    //i->x + x->i의 최댓값을 구함
	for (int i = 1; i <= n; i++) {
		if (i == x) continue;
		int temp = arr[i][x] + arr[x][i];
		if (mx < temp) mx = temp;
	}
	cout << mx;
	return 0;
}