[백준/17835][C++] 면접보는 승범이네

문제

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

17835번: 면접보는 승범이네

풀이

다시 C++로 오게된 이유는,,,, 최근 코테보는 기업들이 Python으로 시험을 못보게해서...  C++은 자료형을 신경써야하는게 무척이나 귀찮다....확실히 파이썬이 편하지만 어쩌겠냐~

이번 문제를 통해 다익스트라를 다시 한 번 공부했다. 개인적으로 다익스트라 너무 어렵지만.. 외우면 되니까 자주 풀어야겠다.

이번엔 역방향 그래프가 필요했다. 왜냐? 우선 모든 집에서 면접장까지의 최단 거리를 구하기 위해 다익스트라를 돌리면 시간초과가 난다.

따라서 면접장부터 특정 집까지 최단거리를 구해준다. 그래서 역방향 그래프가 필요하다. 면접장에서 지원자들 위치까지의 최단거리를 저장해나간다.

면접장이 여러개더라도 괜찮다. 즉 출발지점이 여러개인 다익스트라는 어딘가의 면접장에서부터 집까지의 가장 짧은 거리만 갱신해준다. 다익스트라는 현재까지 최단거리가 보장된 정점들의 비용을 기반으로 아직 최단거리가 보장되지 않은 정점 중 비용이 가장 작은 정점을 확장해나가야한다. --> 시작점이 여러개면 어떤 시작점에서 출발한지는 알 수 없지만 어딘가의 시작점에서 출발해 임의의 노드까지 가장 짧은 거리는 보장이 된다.

https://m.blog.naver.com/fbfbf1/222662390674 해당블로그 참고했다.......ㅎ 난 성장하려면 멀었다~

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m, k;
vector<pair<int, ll>> graph[100005];
const ll INF = 1e18;
priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> pq;
ll d[100005];
int ks[100005];
int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m >> k;
	while (m--) {
		int u, v;
		ll c;
		cin >> u >> v >> c;
		graph[v].push_back({ c,u });
	}
	fill(d, d + n + 3, INF);
	while (k--) {
		int i;
		cin >> i;
		d[i] = 0;
		pq.push({ 0,i }); //시작점이 여러개인것
	}
	//다익스트라 알고리즘
	while (!pq.empty()) {
		auto cur = pq.top();
		pq.pop();
		if (d[cur.second] != cur.first) continue;
		for (auto nxt : graph[cur.second]) {
			if (d[nxt.second] > d[cur.second] + nxt.first) {
				d[nxt.second] = d[cur.second] + nxt.first;
				pq.push({ d[nxt.second],nxt.second });
			}
		}
	}
	int idx = -1;
	ll maxnum = -1;
	for (int i = 1; i <= n; i++) {
		if (maxnum < d[i]) {
			idx = i;
			maxnum = d[i];
		}
	}
	cout << idx << "\n" << maxnum;
	return 0;
}