백준 : 17835번 면접보는 승범이네 다익스트라(c++)

백준 링크

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

17835번: 면접보는 승범이네

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	256 MB	2919	802	590	25.096%

문제

마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 1차 서류전형이 끝난 뒤 합격자들은 면접을 준비하게 되었다.

면접자들은 서로 다른 N개의 도시에 거주한다. 승범이는 면접자들의 편의를 위해 거주 중인 N개 도시 중 K개의 도시에 면접장을 배치했다. 도시끼리는 단방향 도로로 연결되며, 거리는 서로 다를 수 있다. 어떤 두 도시 사이에는 도로가 없을 수도, 여러 개가 있을 수도 있다. 또한 어떤 도시에서든 적어도 하나의 면접장까지 갈 수 있는 경로가 항상 존재한다.

모든 면접자는 본인의 도시에서 출발하여 가장 가까운 면접장으로 찾아갈 예정이다. 즉, 아래에서 언급되는 '면접장까지의 거리'란 그 도시에서 도달 가능한 가장 가까운 면접장까지의 최단 거리를 뜻한다.

속초 출신 승범이는 지방의 서러움을 알기에 각 도시에서 면접장까지의 거리 중, 그 거리가 가장 먼 도시에서 오는 면접자에게 교통비를 주려고 한다.

승범이를 위해 면접장까지의 거리가 가장 먼 도시와 그 거리를 구해보도록 하자.

입력

첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다.

다음 M개의 줄에 걸쳐 한 줄마다 도시의 번호 U, V(U ≠ V)와 도로의 길이 C(1 ≤ C ≤ 100,000)가 공백을 두고 순서대로 주어진다. 이는 도시 U에서 V로 갈 수 있는 도로가 존재하고, 그 거리가 C라는 뜻이다.

마지막 줄에 면접장이 배치된 도시의 번호 K개가 공백을 두고 주어진다.

출력

첫째 줄에 면접장까지 거리가 가장 먼 도시의 번호를 출력한다. 만약 그런 도시가 여러 곳이면 가장 작은 번호를 출력한다.

둘째 줄에 해당 도시에서 면접장까지의 거리를 출력한다.

예제 입력 1 복사

6 10 2
2 6 2
1 4 1
6 1 5
2 5 1
5 1 4
4 5 6
6 2 3
3 5 1
3 1 1
5 2 2
1 2

예제 출력 1 복사

4
8

코드 풀이

오늘 문제는 다익스트라 응용문제로 이전에 다익스트라를 계속해서 풀어왔지만 생각보다 오래 걸렸던 문제다.

(정답 비율이 25퍼라니..)

풀이 순서

• 입력으로 주어진 노드를 그래프에 연결한다(역방향으로 연결해야 함 이유는 아래에서 설명)
• 면접장 위치를 전부 벡터에 저장
• 다익스트라 실행( 기존 다익스트라와 다른 부분은 시작지점이 하나가 아니다 = 면접장 위치를 전부 큐에 넣는다)
• 다익스트라 종료 후 가장 거리가 먼 도시와 거리를 추출하여 출력

주의해야 할 점

• 노드를 역방향으로 연결하는 이유는 면접장에서 각 도시까지의 거리를 구하면 되기 때문 각 도시에서 면접장까지의 거리를 하나하나 계산할 필요가 없다.
• 다익스트라라고 해서 시작지점이 하나라는 고정관념은 버리자(면접장 전부를 우선순위 큐에 한 번에 넣고 시작해도 된다는 것)
• 맥스값을 추출할 때 혹시 모를 예외처리 하기 Dist[i] != INF 조건에 넣기

코드

#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX 100001
#define INF 1e18

int N, M, K;

vector<pair<int, int>> Graph[MAX];
vector<long long> Dist;
vector<int> vecInterviewPlace;

void Dijkstra()
{
	Dist.resize(N + 1);

	fill(Dist.begin(), Dist.begin() + N + 1, INF);

	priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
	size_t InterViewPlaceSize = vecInterviewPlace.size();
	// 모든 면접장소 위치를 큐에 넣는다.
	for (auto& Place : vecInterviewPlace)
	{
		pq.push({ 0, Place });
		Dist[Place] = 0;
	}

	// 모든 면접장소 위치로부터 다익스트라 실행
	while (!pq.empty())
	{
		int CurNode = pq.top().second;
		long long CurCost = pq.top().first;
		pq.pop();

		if (Dist[CurNode] < CurCost)
			continue;

		int Size = static_cast<int>(Graph[CurNode].size());
		for (int i = 0; i < Size; ++i)
		{
			int NextNode = Graph[CurNode][i].first;
			long long NextCost = Graph[CurNode][i].second + CurCost;

			if (Dist[NextNode] > NextCost)
			{
				pq.push({ NextCost, NextNode });
				Dist[NextNode] = NextCost;
			}
		}
	}
}

void GetMaxPair(pair<int, long long>& OutInterView)
{
	for (int i = 1; i <= N; ++i)
	{
		if (OutInterView.second < Dist[i] && Dist[i] != INF)
		{
			OutInterView.first = i;
			OutInterView.second = Dist[i];
		}
	}
}

int main()
{
	cin >> N >> M >> K;

	for (int i = 0; i < M; ++i)
	{
		int CityA, CityB, Cost;
		cin >> CityA >> CityB >> Cost;

		Graph[CityB].push_back({ CityA, Cost });
	}

	pair<int, long long> MaxPair = {};

	vecInterviewPlace.resize(N + 1);
	for (int i = 0; i < K; ++i)
	{
		cin >> vecInterviewPlace[i];
	}


	// 다익스트라 실행
	Dijkstra();

	// 맥스값 추출
	GetMaxPair(MaxPair);

	cout << MaxPair.first << '\n' << MaxPair.second;

	return 0;
}