문제
풀이
다익스트라 알고리즘 응용문제이다. a, b 정점을 지나치면서 최종 지점까지 최소비용으로 도달하게 하는 문제이다. a, b 정점을 지나는 경로는 크게 두 가지가 있는데, 1->a->b->N, 1->b->a->N이 되겠다. 그래서 다익스트라 알고리즘으로 ‘1->a’, ‘a->b’, ‘b->N’ 경로와 ‘1->b’, ‘b->a(a->b와 동일)’, ‘a->N’ 경로를 각각 구해 더한 경로 중 작은 값을 출력하게 하면 되는 문제이다. 만약 그 중 끊어져있는 부분이 있어 초기값에서 변하지 않았다면, -1을 출력하게 하였다.
소스 코드
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
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
vector<pair<int, int>> map[801];
vector<int> dist(801);
int N, E;
int dijkstra(int start, int end){
for(int i = 1; i<=N; i++){
dist[i] = INT_MAX;
}
priority_queue<pair<int, int>> q; // (value, to)
dist[start] = 0;
q.push(make_pair(0, start));
while(!q.empty()){
int from = q.top().second;
int value = -q.top().first;
q.pop();
for(int i = 0; i<map[from].size(); i++){
int next = map[from][i].first;
int ncost = map[from][i].second;
if(dist[next] > value + ncost){
dist[next] = value + ncost;
q.push(make_pair(-dist[next], next));
}
}
}
return dist[end];
}
int main(){
scanf("%d %d", &N, &E);
for(int i = 0; i<E; i++){
int from, to, value;
scanf("%d %d %d", &from, &to, &value);
map[to].push_back(make_pair(from, value));
map[from].push_back(make_pair(to, value));
}
int a, b;
scanf("%d %d", &a, &b);
//1->a->b->N
int route_1;
int a1 = dijkstra(1, a);
int a2 = dijkstra(a, b);
int a3 = dijkstra(b, N);
if(a1 == INT_MAX || a2 == INT_MAX || a3 == INT_MAX) route_1 = INT_MAX;
else route_1 = a1 + a2 + a3;
//printf("a1 = %d, a2 = %d, a3 = %d\n", a1, a2, a3);
//1->b->a->N
int route_2;
int b1 = dijkstra(1, b);
int b2 = dijkstra(b, a);
int b3 = dijkstra(a, N);
if(b1 == INT_MAX || b2 == INT_MAX || b3 == INT_MAX) route_2 = INT_MAX;
else route_2 = b1 + b2 + b3;
//printf("b1 = %d, b2 = %d, b3 = %d\n", b1, b2, b3);
if(route_1 == INT_MAX && route_2 == INT_MAX) printf("-1\n");
else printf("%d\n", min(route_1, route_2));
}
