BOJ-17835 면접보는 승범이네

필요한 지식

1. 다익스트라

접근

• 정말 오랜만에 푸는 다익스트라 문제였다.
• 문제에선 면접장까지 거리가 가장 먼 도시의 번호를 출력하라고 하지만 입력으로는 면접장으로 향하는 단방향 길들을 주기때문에 입력의 U와 V를 뒤집어서 저장해준다.
• dist 배열을 면접장이 위치하는 도시는 0으로 아니라면 1e17로 초기화 해주며 우선순위큐에 넣었다.
• 아래 코드가 없으면 시간초과가 난다. 오랜만에 봐서 또 까먹었다...

if (dist[cur.e] < cur.val) continue;

코드(C++)

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> p;
typedef struct node {
	ll e, val;
	bool operator < (const node& tmp) const {
		return val > tmp.val;
	}
};
priority_queue<node>pq;
vector<vector<p>>v;
ll pos[100001], dist[100001], n, m, k;
p dijkstra() {
	for (int i = 1; i <= n; i++) {
		ll cost = 1e17;
		if (pos[i]) cost = 0;
		pq.push(node{ i,cost });
		dist[i] = cost;
	}
	while (!pq.empty()) {
		auto cur = pq.top();
		pq.pop();
		if (dist[cur.e] < cur.val) continue;
		for (int i = 0; i < v[cur.e].size(); i++) {
			ll next = v[cur.e][i].first;
			ll cost = v[cur.e][i].second;
			if (dist[next] > cur.val + cost) {
				dist[next] = cur.val + cost;
				pq.push(node{ next,dist[next] });
			}
		}
	}
	p ans = { 0,0 };
	for (int i = 1; i <= n; i++) {
		if (dist[i] != 1e17 && ans.first < dist[i]) ans = { dist[i],i };
	}
	return ans;
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	v.resize(n + 1);
	for (int i = 0; i < m; i++) {
		int s, e, c; cin >> s >> e >> c;
		v[e].push_back({ s,c });
	}
	for (int i = 0; i < k; i++) {
		int x; cin >> x;
		pos[x] = 1;
	}
	p res = dijkstra();
	cout << res.second << "\n" << res.first;
	return 0;
}

---

결과