백준1162 도로포장

작성일 | In

문제 링크

  • http://icpc.me/1162

문제 출처

  • 2009 February Gold 3번

사용 알고리즘

  • Dijkstra

시간복잡도

  • O(MK log NK)

풀이

dist[v][k] = 1번 도시에서 v번 도시까지 k개의 도로를 포장해서 가는 최단 거리 로 정의해서 다익스트라를 돌리면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> p;

struct asdf{
	ll node;
	ll cost;
	ll cnt;

	bool operator < (const asdf x) const {
		return cost > x.cost;
	}
};
ll n, m, k;

vector<p> g[10101];

ll dist[10101][22];

void dijkstra(){
	memset(dist, 0x3f, sizeof dist);
	priority_queue<asdf> pq; pq.push({ 1, 0, 0 });
	dist[1][0] = 0;
	while (pq.size()){
		ll now = pq.top().node;
		ll cost = pq.top().cost;
		ll cnt = pq.top().cnt;
		pq.pop();
		if (cost > dist[now][cnt]) continue;
		for (auto i : g[now]){
			ll nxt = i.first;
			ll nxtCost = cost + i.second;

			if (nxtCost < dist[nxt][cnt]){
				dist[nxt][cnt] = nxtCost;
				pq.push({ nxt, nxtCost, cnt });
			}
			if (cnt < k && cost < dist[nxt][cnt + 1]){
				dist[nxt][cnt + 1] = cost;
				pq.push({ nxt, cost, cnt + 1 });
			}
		}
	}
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++){
		int s, e, x; cin >> s >> e >> x;
		g[s].push_back({ e, x });
		g[e].push_back({ s, x });
	}
	dijkstra();
	ll ans = 1e18;
	for (int i = 0; i <= k; i++) ans = min(ans, dist[n][i]);
	cout << ans;
}