문제
풀이
다익스트라 응용 문제이다. 이 문제 역시, g, h를 지나면서 final 지점에 도착했을 때 가장 최소 비용으로 가는 경로를 확인하는 문제이다. 결과적으로, start -> g -> h -> final or start -> h -> g -> fianl
의 경로 중에 start --> final과 같은 비용으로 가는 경로가 있으면 final을 출력하면 되는 문제이다.
소스 코드
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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#include <algorithm>
using namespace std;
int testcase, n, m, t, s, g, h;
int dist[2001];
vector<pair<int, int>> map[2001];
vector<int> dest(101);
vector<int> result;
int dijkstra(int start, int end){
for(int i = 1; i<=n; i++){
dist[i] = INT_MAX;
}
dist[start] = 0;
priority_queue<pair<int, int>> q;
q.push(make_pair(0, start));
while(!q.empty()){
int cost = -q.top().first;
int now = q.top().second;
q.pop();
for(int i = 0; i<map[now].size(); i++){
int ncost = map[now][i].second;
int next = map[now][i].first;
if(dist[next] > cost + ncost){
dist[next] = cost + ncost;
q.push(make_pair(-dist[next], next));
}
}
}
return dist[end];
}
int main(){
scanf("%d", &testcase);
for(int i = 0 ; i<testcase; i++){
scanf("%d %d %d", &n, &m, &t);
scanf("%d %d %d", &s, &g, &h); // s : 시작점, g, h : 반드시 거쳐야 하는 지점
for(int i = 0; i< 2001; i++){
map[i].clear();
}
dest.clear();
result.clear();
for(int i = 0; i<m; i++){
int from, to, value;
scanf("%d %d %d", &from, &to, &value);
map[from].push_back(make_pair(to, value));
map[to].push_back(make_pair(from, value));
}
for(int i = 0; i<t; i++){
scanf("%d", &dest[i]);
}
for(int i = 0; i<t; i++){
int route1;
int a1 = dijkstra(s, g);
int a2 = dijkstra(g, h);
int a3 = dijkstra(h, dest[i]);
if(a1 == INT_MAX || a2 == INT_MAX || a3 == INT_MAX) route1 = -1;
else route1 = a1+a2+a3;
//printf("%d %d %d\n", a1, a2, a3);
int route2;
int b1 = dijkstra(s, h);
int b2 = dijkstra(h, g);
int b3 = dijkstra(g, dest[i]);
if(b1 == INT_MAX || b2 == INT_MAX || b3 == INT_MAX) route2 = -1;
else route2 = b1+b2+b3;
//printf("%d %d %d\n", b1, b2, b3);
int route3 = dijkstra(s, dest[i]);
//printf("route3 = %d\n", route3);
if(route1 == route3 || route2 == route3) result.push_back(dest[i]);
}
sort(result.begin(), result.end());
for(int i = 0; i<result.size(); i++){
printf("%d ", result[i]);
}
printf("\n");
}
}
