백준 1238번

백준 1238번 (파티)

이 문제는 N개의 마을에 있는 학생들이 X번 마을로 모여 파티를 하는데 이때 왕복시간이 가장 오래 걸리는 학생을 찾는 문제이다. 도로가 단방향으로 주어지기에 오는 동선과 가는 동선이 다를 수 있다는 것을 염려해야하는 문제다.

처음 문제를 읽고 해결 방안을 생각해봤을 때, 쉽게 플로이드 와샬로 풀어야겠다는 생각을 했다. 크게 두 가지 근거가 있었다.

우선 N의 범위가 1000까지 밖에 안됐다. 플로이드 와샬로도 충분히 1초 안에 해결할 수 있다고 생각하였다. 그리고 두 번째로, 오는 최단 거리와 가는 최단 거리가 다를 수 있으며, X번 마을로 오는 모든 마을의 오가는 최단 거리를 서로 비교해야하기에 플로이드 와샬이 해결하기에 용이할 것이라고 생각했다.

실제로도 구현도 간단하고 쉽게 해결할 수 있었다.

#include <bits/stdc++.h>

using namespace std;

int road[1005][1005];
int n, m, x;

int main() {
	scanf_s("%d %d %d", &n, &m, &x);

	memset(road, 0x3f, sizeof(road));

	for (int i = 0; i < m; i++) {
		int s, e, t;
		scanf_s("%d %d %d", &s, &e, &t);
		road[s][e] = t;
	}

	for (int k = 1; k <= n; k++) 
		for (int i = 1; i <= n; i++) 
			for (int j = 1; j <= n; j++) 
				if (road[i][j] > road[i][k] + road[k][j]) 
					road[i][j] = road[i][k] + road[k][j];

	int ans = 0;

	for (int i = 1; i <= n; i++) {
		if (i == x)
			continue;
		int tmp = road[i][x] + road[x][i];
		ans = max(ans, tmp);	
	}

	printf("%d", ans);

	return 0;
}