백준] 1238 - 파티(USACO 2007)

시간 제한 : 1초

메모리 제한 : 128MB

입력

첫째 줄에 N(1 <= N <= 1,000), M(1 <= M <= 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

소스코드

#include <iostream>
#define INF 1000000000
using namespace std;
int graph[1000][1000], n;
void Floyd()
{
	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (graph[i][k] + graph[k][j] < graph[i][j])
					graph[i][j] = graph[i][k] + graph[k][j];
}
int main(void)
{
	int m, x, v1, v2, w, max, weight;
	cin >> n;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			graph[i][j] = INF;
	for (int i = 0; i < n; i++)
		graph[i][i] = 0;

	cin >> m >> x;
	for (int i = 0; i < m; i++)
	{
		cin >> v1 >> v2 >> w;
		if(graph[v1-1][v2-1] > w)
			graph[v1 - 1][v2 - 1] = w;
	}

	Floyd();

	max = -1;
	for (int i = 0; i < n; i++)
	{
		weight = graph[i][x - 1] + graph[x - 1][i];
		max = max < weight ? weight : max;
	}
	cout << max;
}

Tip

플로이드-워셜 알고리즘을 응용하는 문제로, 오고 가는데 사용되는 시간들을 계산하면 된다.