BOJ 15292 Journey from Petersburg to Moscow

문제 링크입니다. 동명의 도서가 있네요.

문제 요약

1번 정점에서 N번 정점으로 가는 최소 비용을 구해야 합니다. 그런데 이제 경로의 제일 비싼 K개 간선에서만 돈을 내는.

기준치 정하기

K 제한이 없다면 다익스트라 알고리즘으로 문제를 해결할 수 있습니다. 이는 즉 최소 비용 경로의 간선 수가 K개 이하면 그 경로의 비용이 실제 답이 됨을 뜻합니다.

K 제한이 있는 상황에서의 최소 비용 경로는, 가장 비싼 K개의 경로의 비용은 그대로고, 경로 위의 나머지 간선의 비용은 0인 상태입니다. 이때 경로를 이루는 간선 개수는 K개 초과라고 가정합시다.

우리는 가장 비싼 K개의 간선의 비용을 관리하는 대신, K번째로 비싼 간선의 비용을 무엇으로 할지를 결정해 둔 채로 문제를 바라볼 수 있습니다. 이러고 나서 일단 K개 제한을 무시하고 최소 비용 경로를 찾읍시다. 우리는 지금 상황에서 그냥 모든 간선에 K번째로 비싼 간선의 비용만큼의 할인이 들어가고 있다고 생각할 수 있습니다. (비용이 0 미만이 되지는 않습니다.)

Aliens Trick 비슷한 거 하기

이렇게 찾은 경로의 비용 합에 K번째로 비싼 간선의 비용을 K배 해서 더해 주면, 현재 경로에서 정확히 K개의 간선의 비용이 기준 비용보다 비싸거나 같은 경우에 문제의 조건을 만족하는 상태가 됩니다.

• 만약 기준 비용보다 비싼 간선이 K개 초과인 경우, 제일 비싼 K개의 간선의 비용에 추가적인 비용이 붙은 상태가 됩니다. 기준 비용을 더 높게 잡았을 때 더 좋은 해가 반드시 존재합니다.
• 만약 기준 비용보다 비싼 간선이 K개 미만인 경우, 기준 비용보다 싼 간선의 비용이 기준 비용인 것처럼 계산됩니다. 기준 비용을 더 낮게 잡았을 때 더 좋은 해가 반드시 존재합니다.

이를 잘 증명하면, 결국 각 간선의 비용을 기준 비용으로 잡은 상태에서 다익스트라를 돌려보면서 그중 최솟값을 답으로 정하는 것으로 문제를 해결할 수 있다는 사실을 알 수 있습니다. 물론 기준 비용을 잡지 않은 상태에서의 최소 비용 역시 고려해 주어야 합니다.

코드

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

vector<pll> e[3030];
ll d[3030], n, m, k, ans = 1e18;

ll dijk(ll kth){
	memset(d, 1, sizeof(d)); d[1] = 0;
	priority_queue<pll> pq; pq.push({0, 1});
	while(pq.size()){
		auto [w, now] = pq.top(); pq.pop(); if(-w > d[now]) continue;
		for(auto [nw, nxt] : e[now]) if(max(0LL, nw-kth)-w < d[nxt]){
			d[nxt] = max(0LL, nw-kth)-w;
			pq.push({-d[nxt], nxt});
		}
	}
	return d[n];
}

int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	vector<ll> st(1,0); cin >> n >> m >> k;
	while(m--){
		ll u, v, w; cin >> u >> v >> w;
		e[u].push_back({w, v});
		e[v].push_back({w, u});
		st.push_back(w);
	}
	for(auto w : st) ans = min(ans, dijk(w)+w*k);
	cout << ans;
}