[백준 21940] 가운데에서 만나기 (C++)

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

21940번: 가운데에서 만나기

문제

---

준형이는 내일 친구들을 만나기로 했다. 준형이와 친구들은 서로 다른 도시에 살고 있다.

도시를 연결하는 도로는 일방 통행만 있어서 도시 A_i에서 도시 B_i로 가는 시간과 도시 B_i에서 도시 A_i로 가는 시간이 다를 수 있다.

준형이와 친구들은 아래 조건을 만족하는 도시 X를 선택하여 거기서 만나려고 한다.

• 왕복시간은 자신이 살고 있는 도시에서 도시 X로 이동하는 시간과 도시 X에서 다시 자신이 살고 있는 도시로 이동하는 시간을 합한 것이다.
• 준형이와 친구들이 도로를 이용하여 갈 수 있는 도시만 선택한다.
• 준형이와 친구들의 왕복시간 들 중 최대가 최소가 되는 도시 X를 선택한다.
• 준형이와 친구들이 이동할 수 있는 도시가 최소한 하나 이상이 있음을 보장한다.

도시가 많다보니 계산하기 힘들다. 준형이와 친구들을 대신하여 도시 X를 알려주자.

입력

---

첫 번째 줄에는 도시의 개수 N과 도로의 개수 M이 주어진다.

두 번째 줄부터 M + 1줄까지 도시 A_i, 도시 B_i, 도시 A_i에서 도시 B_i로 이동하는데 걸리는 시간 Ti가 공백으로 구분되어 주어진다.

 M + 2줄에는 준형이와 친구들의 총 인원 K가 주어진다.

 M + 3줄에는 준형이와 친구들이 살고 있는 도시의 번호 Ci가 공백으로 구분되어 주어진다.

출력

---

위 조건을 만족하는 도시 X의 번호를 출력한다. 만약 가능한 도시 X가 여러 개인 경우는 도시의 번호를 오름차순으로 출력한다.

 

문제 풀이

---

모든 도시 중에서 가장 짧은 경로를 찾는 문제이므로 플로이드-워셜 알고리즘을 사용하는 문제이다.

중간에 방문하여 거리가 짧아지는 노드를 찾도록 k-i-j 순의 3중 반복문을 돌려야한다는 것을 잊지 말도록 하자.

플로이드-워셜 알고리즘을 통해 모든 노드와 노드 사이의 최단 거리를 구했다면 모든 도시 중 한 친구의 왕복 시간이 가장 긴 것이 최소가 되는 도시를 벡터에 저장하여 출력한다.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 200000000
using namespace std;
int N, M, K;
int** arr;
int* friends;
vector<int> minCities;
int minCost = 987654321;

void floydWarshall()
{
	for (int k = 1; k < N + 1; k++)
	{
		for (int i = 1; i < N + 1; i++)
		{
			for (int j = 1; j < N + 1; j++)
			{
				if (arr[i][k] + arr[k][j] < arr[i][j])
				{
					arr[i][j] = arr[i][k] + arr[k][j];
				}
			}
		}
	}
}

void getMinCity()
{
	for (int i = 1; i < N + 1; i++)
	{
		int maxCost = 0;
		for (int j = 0; j < K; j++)
		{
			maxCost = max(maxCost, arr[i][friends[j]] + arr[friends[j]][i]);
		}
		if (maxCost < minCost)
		{
			minCost = maxCost;
			minCities.clear();
			minCities.push_back(i);
		}
		else if (maxCost == minCost)
		{
			minCities.push_back(i);
		}
	}
}

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

	int start, end, cost;
	cin >> N>>M;
	arr = new int*[N+1];
	for (int i = 0; i < N+1; i++)
	{
		arr[i] = new int[N + 1];
		for (int j = 0; j < N + 1; j++)
		{
			if (i == j)
			{
				arr[i][j] = 0;
			}
			else
			{
				arr[i][j] = INF;
			}
		}
	}
	for (int i = 0; i < M; i++)
	{
		cin >> start >> end >> cost;
		arr[start][end] = cost;
	}
	cin >> K;
	friends = new int[K];
	for (int i = 0; i < K; i++)
	{
		cin >> friends[i];
	}
	floydWarshall();
	getMinCity();
	for (int i = 0; i < minCities.size(); i++)
	{
		cout << minCities.at(i) << " ";
	}
	return 0;
}