[BOJ/Gold 2] 백준 17835 면접보는 승범이네(C++)

문제 링크

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

17835번: 면접보는 승범이네

 

문제

마포구에는 모든 대학생이 입사를 희망하는 굴지의 대기업 ㈜승범이네 본사가 자리를 잡고 있다. 승범이는 ㈜승범이네의 사장인데, 일을 못 하는 직원들에게 화가 난 나머지 전 직원을 해고하고 신입사원을 뽑으려 한다. 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

예제 입력 2

10 20 5
4 1 18
6 1 7
2 4 1
5 6 18
7 6 10
10 6 9
3 2 4
8 3 10
9 8 15
7 1 12
10 7 1
8 1 3
6 5 19
2 9 10
7 2 4
10 3 20
7 10 14
5 7 12
8 4 10
2 5 8
1 8 4 6 7

예제 출력 2

9
15

알고리즘 분류

• 최단 거리 알고리즘

풀이

면접장의 위치 K개를 시작점으로 하는 다익스트라를 수행한다.

도로의 방향이 단방향이고, 면접장의 위치에서 반대로 면접자들이 있는 곳으로 이동하는 것이기 때문에, 도로의 정보를 입력받아 정점과 정점 사이를 연결할 때 반대 방향으로 이어준다. 즉 U->V가 아니라 V->U로 연결시켜 준다.

면접장이 있는 정점이 아니며, 면접장에서 해당 정점까지 이동할 수 있고, 그러한 정점 중에서 번호가 가장 낮은 정점을 최단 거리와 함께 구해준다. 

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 100001
#define LL long long
#define INF 1e11

using namespace std;
int N, M, K;
vector<pair<int, LL> > Edge[MAX];
priority_queue<pair<LL, int> > PQ;
LL Cost[MAX];
vector<int> Point;
LL Len = 0;
int answer;

void Input() {
	cin >> N >> M >> K;
	for (int i = 1; i <= N; i++) {
		Cost[i] = INF;
	}
	for (int i = 0; i < M; i++) {
		int U, V;
		LL C;
		cin >> U >> V >> C;
		Edge[V].push_back(make_pair(U, C));
	}
	for (int i = 0; i < K; i++) {
		int City;
		cin >> City;
		Point.push_back(City);
	}
}

void Dijkstra() {
	while (!PQ.empty()) {
		LL CurCost = -PQ.top().first;
		int CurX = PQ.top().second;
		PQ.pop();

		if (Cost[CurX] < CurCost) {
			continue;
		}

		for (int i = 0; i < Edge[CurX].size(); i++) {
			LL nextCost = Edge[CurX][i].second;
			int nextX = Edge[CurX][i].first;
			if (Cost[nextX] > CurCost + nextCost) {
				Cost[nextX] = CurCost + nextCost;
				PQ.push(make_pair(-Cost[nextX], nextX));
			}
		}
	};
}

void Settings() {
	for (int i = 0; i < Point.size(); i++) {
		Cost[Point[i]] = 0;
		PQ.push(make_pair(0, Point[i]));
	}
	Dijkstra();
}

void Find_Answer() {
	for (int i = 1; i <= N; i++) {
		if ((Cost[i] > 0) && (Cost[i] != INF)) {
			if (Len < Cost[i]) {
				Len = Cost[i];
				answer = i;
			}
		}
	}
	cout << answer << "\n" << Len << "\n";
}

int main() {
	FASTIO
	Input();
	Settings();
	Find_Answer();

	return 0;
}