10217 KCM Travel
알고리즘(다익스트라, DP)
1
2
3
4
5
6
1. 기본적으로 다익스트라를 사용하여 최소경로를 찾아야하는 것을 맞으나, 비용이 넘어버릴경우 이전의 최소경로로 간 것이 의미가 없어진다.
따라서 현재 큐에서 꺼낸 노드가, 이전에 지나간 노드보다 같은 비용일때 더 시간이 많이 걸렸을 경우만 패스.
DP[101][10001] 선언
2. 첫번째를 제외하고, 모든 노드를 INF 로 초기화
3. 다익스트라를 진행하면서, 현재 큐에서 꺼낸 노드의 시간이 DP[현재노드][현재노드의 비용] 보다 클 때 패스 (같은 거는 현재 일 수 있음)
4. 인접한 노드를 업데이트할때, (다음노드로 가는비용 ~ 최대비용) 까지 이미 저장된 값보다 작을 때 DP[다음노드][비용] 을 다음 시간으로 업데이트
코드
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
#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
struct Line {
int to;
int m;
int time;
};
vector<Line> airport[101];
int N, M, K, DP[101][10001];
queue<Line> q;
void dijkstra();
void init() {
for (int i = 1; i <= N; i++) {
airport[i].clear();
for(int j = 1; j<=M; j++)
DP[i][j] = INF;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int tc;
cin >> tc;
for (int i = 0; i < tc; i++) {
cin >> N >> M >> K;
init();
for (int j = 0; j < K; j++) {
int a, b, c, d;
cin >> a >> b >> c >> d;
airport[a].push_back({ b, c, d });
}
dijkstra();
int answer = INF;
for (int j = 1; j <= M; j++)
answer = min(answer, DP[N][M]);
if (answer == INF)
cout << "Poor KCM" << "\n";
else
cout << answer << "\n";
}
}
void dijkstra() {
q.push({1, 0, 0});
while (!q.empty()) {
Line a = q.front();
q.pop();
if (a.time > DP[a.to][a.m])
continue;
for (int j = 0; j < airport[a.to].size(); j++) {
Line next = airport[a.to][j];
int nm = a.m + next.m, nt = a.time + next.time, to = next.to;
if (nm <= M && nt < DP[to][nm]) {
q.push({ to, nm, nt });
for (int k = nm; k <= M; k++)
if(nt < DP[to][k])
DP[to][k] = nt;
}
}
}
}