문제 출처

1. 문제설명

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

  • 첫째 줄에 면접장까지 거리가 가장 먼 도시의 번호를 출력, 둘째 줄에 해당 도시에서 면접장까지의 거리를 출력

  • 문제 분류
    • Graph, Dijkstra


2. 알고리즘 설계

  • 다익스트라로 풀이할 수 있다.
  • 시작 정점들을 전부 우선순위 큐에 넣어주고, 면접장까지의 거리를 갱신시켜주면 된다.
  • 시작 정점들의 최단 면접장까지 거리를 구했다면, 가장 큰 값을 찾으면 된다.
    • max_element 함수를 이용하였다.
    • index를 추출하기 위해서는 index = max_element() - Arr
    • 가장 큰 원소를 추출하는 방법은 Arr[index]를 해주면 되겠다.


3. 전체 코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pli = pair<ll,int>;

const int SZ = 100'002;
int n, m, k;
ll Dist[SZ], INF = 0x7f7f7f7f7f7f;
vector<pli> adj[SZ];
priority_queue<pli, vector<pli>, greater<pli>> pq;

void solve() {
	while(!pq.empty()) {
		int u, v;
		ll w, dw;

		tie(w, u) = pq.top();
		pq.pop();

		if(Dist[u] != w) continue;

		for(auto nxt : adj[u]) {
			tie(dw, v) = nxt;
			dw += w;

			if(Dist[v] > dw) {
				Dist[v] = dw;
				pq.push({dw, v});
			}
		}
	}
}

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

	cin >> n >> m >> k;
	fill(Dist+1, Dist+n+1, INF);

	for(int u, v, w; m--;) {
		cin >> u >> v >> w;
		adj[v].push_back({w, u});
	}

	for(int u; k--;) {
		cin >> u;
		Dist[u] = 0;
		pq.push({0, u});
	}

	solve();

	int target_idx = max_element(Dist+1, Dist+n+1) - Dist;
	cout << target_idx << '\n' << Dist[target_idx];

	return 0;
}