문제
풀이
다익스트라 응용 문제이다. 기존에 출발지, 도착지, 거리만 존재하던 경우에서 비용까지 고려하는 문제로 확장된 것이다. 기존에 i번째까지 도달하는데 가장 짧은 시간을 의미하는 dist[i]에서 dist[i][j] 는 i에 도달할 때 j비용으로 도달할 수 있는 최소 시간을 의미로 2차원으로 확장해서 풀어지는 문제이다. 기존의 다익스트라 알고리즘에서 크게 바뀐 것은 없고 다만, next_cost <= M이면서 next_time을 더 낮은 값으로 갱신할 수 있는 것들로 바꿔주면서 다익스트라를 진행하였다.
소스 코드
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include <iostream>
#include <vector>
#include <queue>
#define INF 1e9
using namespace std;
vector<pair<pair<int, int>, int>> map[101];
int dist[101][10001];
int N, M, K;
void init(){
for(int i = 0; i<101; i++){
map[i].clear();
for(int j = 0; j<10001; j++){
dist[i][j] = INF;
}
}
}
void dijkstra(){
for(int i = 0 ; i<=N; i++){
for(int j = 0; j<=M; j++){
dist[i][j] = INF;
}
}
dist[1][0] = 0;
priority_queue<pair<pair<int, int>, int>> q; // 시간, 출발지, 비용
q.push(make_pair(make_pair(0, 1), 0));
while(!q.empty()){
int current_time = -q.top().first.first;
int current_city = q.top().first.second;
int current_cost = q.top().second;
q.pop();
if(dist[current_city][current_cost] < current_time) continue; // 효율성을 올리기 위해 continue문 추가
for(int i = 0; i<map[current_city].size(); i++){
int next_time = current_time + map[current_city][i].second;
int next_city = map[current_city][i].first.first;
int next_cost = current_cost + map[current_city][i].first.second;
if(next_cost <= M && next_time < dist[next_city][next_cost]){
for(int i = next_cost; i<=M; i++){
if(dist[next_city][i] <= next_time) break; // 효율성을 올리기 위해 break문 추가
dist[next_city][i] = next_time;
}
dist[next_city][next_cost] = next_time;
q.push(make_pair(make_pair(-next_time, next_city), next_cost));
}
}
}
}
int main(){
int T;
scanf("%d", &T);
for(int i = 0; i<T; i++){
scanf("%d %d %d", &N, &M, &K);
for(int j = 0; j<K; j++){
int u, v, c, d;
scanf("%d %d %d %d", &u, &v, &c, &d); // 출발지, 도착지, 비용, 이동시간
map[u].push_back(make_pair(make_pair(v, c), d)); // 도착지, 비용, 이동시간
}
dijkstra();
int ans = INF;
for(int k = 0 ; k<=M; k++){
if(dist[N][k] < ans) ans = dist[N][k];
}
if(ans == INF) printf("Poor KCM\n");
else printf("%d\n", ans);
init();
}
}
