집과 가장 가까운 면접장까지의 거리가 제일 먼 사람이 사는 도시와 거리를 출력하는 문제입니다.
그래프가 주어질 때 최소 거리의 최대를 구하는 문제입니다.
가중치가 없거나 트리라면 BFS로 구할 수 있지만 둘 다 아니므로 다익스트라를 쓰겠습니다.
N이 최대 10만이고, M이 최대 50만이므로 면접자들이 사는 모든 도시에서 면접장까지의 최소 거리를 구하면 너무 오래 걸립니다.
그래서 모든 도시 → 면접장이 아닌 면접장 → 모든 도시의 최소 거리를 구하겠습니다.
면접장 → 모든 도시를 구하기 때문에 그래프를 입력받을 때 간선을 반대로 입력받아야 합니다.
또 모든 면접장을 기준으로 다익스트라를 하면 면접장의 개수가 최대 N이므로 안됩니다.
시간을 줄이기 위해 모든 면접장을 우선순위 큐에 한 번에 넣고 거리를 구하겠습니다.
우선순위 큐에 한 번에 넣어도 한 면접장에서부터 거리가 아닌 가장 가까운 면접장과의 거리를 구하는 것이기 때문에 상관없습니다.
다익스트라는 기본 다익스트라 구조를 구현하면 됩니다.
다익스트라를 알고 있으면 쉽게 풀 수 있는 문제입니다!!
#include <bits/stdc++.h>
#define FIO ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define vi vector <int>
#define vvi vector <vi>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fs first
#define sd second
#define eb emplace_back
using namespace std;
int main() {
FIO;
int n, m, k; cin >> n >> m >> k;
vector <vector <pii>> adj(n + 1);
FOR(i, 1, m) {
int a, b, w;
cin >> a >> b >> w;
adj[b].eb(w, a);
}
priority_queue <pll> q;
vector <ll> dist(n + 1, 1e18);
FOR(i, 1, k) {
int x; cin >> x;
q.emplace(0, x);
dist[x] = 0;
}
while (q.size()) {
pll now = q.top(); q.pop();
now.fs = -now.fs;
if (dist[now.sd] < now.fs) continue;
for (pii next : adj[now.sd]) {
if (dist[next.sd] <= dist[now.sd] + next.fs) continue;
dist[next.sd] = dist[now.sd] + next.fs;
q.emplace(-dist[next.sd], next.sd); // push
}
}
pll ans = { 0, 1e18 };
for (int i = 1; i <= n; i++) // 최댓값 구하기
if (dist[i] > ans.fs) ans = { dist[i], i };
cout << ans.sd << '\n' << ans.fs << '\n';
return 0;
}