[2019 홍익대학교 프로그래밍 경진대회] 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. N개 정점에 대해 K개 면접장으로의 distance를 다 구해서 최솟값을 따로 저장후에 재정렬 후 출력.

=> N번 다익스트라 돌리는 것에 시간초과

2. 어떤 정점에서 단방향으로 목적지에 간다면 반대 방향으로 저장시 목적지에서 어떤 정점으로의 거리 구할 수 있음.

따라서 K개의 정점에서 시작한 distance를 구해서 최솟 값 찾기 => 역시 시간초과

3. 생각해보면 여러번 다익스트라를 돌릴필요가 없다.

1에서 K개의 면접장에 각 도착하는 거리중 최솟값만이 필요한 것이므로 K에서 시작하고 거리가 0인 것으로 우선순위 큐를 채운 뒤 한번의 다익스트라를 통해 얻어낸 최솟값으로 바로 구할 수 있다.

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;

int N, M, K;
#define INF 10000000000000
vector<pair<long long, long long> > vec[100001];


int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		vec[b].push_back({ a,c });
	}

	vector<long long> distance(N + 1, INF);
	priority_queue < pair<long long, long long>, vector<pair<long long, long long> >, greater<pair<long long, long long> > > pq;
	for (int i = 0; i < K; i++)
	{
		int k;
		cin >> k;
		distance[k] = 0;
		pq.push({ 0,k });
		
	}

	while (!pq.empty())
	{
		long long cost = pq.top().first;
		long long cur = pq.top().second;
		pq.pop();
		if (distance[cur] < cost)
			continue;
		for (int i = 0; i < vec[cur].size(); i++)
		{
			long long next_cost = cost + vec[cur][i].second;
			long long next = vec[cur][i].first;
			if (distance[next] > next_cost)
			{
				distance[next] = next_cost;
				pq.push({ next_cost,next });
			}
		}
	}

	long long maxa = 0;
	long long idx ;
	for (int i = 1; i <= N; i++)
	{
		if (maxa < distance[i])
		{
			maxa = distance[i];
			idx = i;
		}
	}
	cout << idx << "\n" << maxa;
	
}