[백준/BOJ] 백준 1238번 : 파티

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

1238번: 파티

플로이드 알고리즘을 이용해 각 정점까지 가는 최단 경로를 찾고 x위치까지 왕복 가장 오래 걸리는 학생의 시간을 찾는다.

 

코드

#include <iostream>
#include <algorithm>
using namespace std;

int adj[1001][1001];
int n, m, x, t;

int Solve(int x)
{
	int ret = -1;

	//플로이드 알고리즘을 이용해 각 정점까지 가는 최단 경로를 찾는다
	for (int i = 1; i <= n; i++)
		adj[i][i] = 0;

	for (int k = 1; k <= n; k++)
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				adj[i][j] = min(adj[i][j], adj[i][k] + adj[k][j]);

	//x위치까지 왕복 가장 오래 걸리는 학생의 시간을 찾는다
	for (int i = 1; i <= n; i++)
	{
		ret = max(ret, adj[i][x]+adj[x][i]);
	}

	return ret;
}

//처음 그래프를 초기화 할때 모든 노드가 연결되어 있지 않다는 의미로 매우 큰 수를 넣는다
void adjMake()
{
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			adj[i][j] = 987654321;
}

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	int u, v;

	cin >> n >> m >> x;

	adjMake();

	for (int i = 0; i < m; i++)
	{
		cin >> u >> v >> t;
		adj[u][v] = t;
	}

	cout << Solve(x);
	
	return 0;
}