문제링크 : https://www.acmicpc.net/problem/1504
이 문제는, 꼭 거쳐야만 하는 2개의 정점을 거친 경우의 1부터 n까지의 최단경로를 구하는 문제 입니다.
따라서 우리는 2개 정점을 거치는 경우의 수를 구해야 합니다.
두 정점을 s1, s2라고 한다면
1 - s1 - s2 - n
또는,
1 - s2 - s1 - n
위 두가지의 경우중 거리가 더 짧은 것을 선택하면 됩니다.
저는 다익스트라를 6번 반복하였지만, 다른 해를 보니 3번만 해도 된다고 합니다.
그 이유는 이 그래프는 양방향 그래프이기 때문에 s1-s2와 s2-s1은 같은 거리를 갖을 것이고 따라서 1 - s1 과 1- s2를 구하는데 다익스트라 1번, n - s2와 n - s1를 구하는데 다익스트라 2번, s1 = s2를 구하는데 다익스트라 3번 이면 됩니다.
소스코드 :
이 문제는, 꼭 거쳐야만 하는 2개의 정점을 거친 경우의 1부터 n까지의 최단경로를 구하는 문제 입니다.
따라서 우리는 2개 정점을 거치는 경우의 수를 구해야 합니다.
두 정점을 s1, s2라고 한다면
1 - s1 - s2 - n
또는,
1 - s2 - s1 - n
위 두가지의 경우중 거리가 더 짧은 것을 선택하면 됩니다.
저는 다익스트라를 6번 반복하였지만, 다른 해를 보니 3번만 해도 된다고 합니다.
그 이유는 이 그래프는 양방향 그래프이기 때문에 s1-s2와 s2-s1은 같은 거리를 갖을 것이고 따라서 1 - s1 과 1- s2를 구하는데 다익스트라 1번, n - s2와 n - s1를 구하는데 다익스트라 2번, s1 = s2를 구하는데 다익스트라 3번 이면 됩니다.
소스코드 :
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <string>
#define INF 987654321
using namespace std;
int main() {
cin.tie(0);
ios_base::sync_with_stdio(false);
int n, e;
cin >> n >> e;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > pq;
vector< vector< pair<int, int> > > graph(n + 1);
vector<int> distance(n + 1, INF);
for (int i = 0; i < e; i++) {
int a, b, c;
cin >> a >> b >> c;
graph[a].push_back({ b,c });
graph[b].push_back({ a,c });
}
int s1, s2;
cin >> s1 >> s2;
pq.push({ 0, 1 });
distance[1] = 0;
// 1 -> s1 and 1 -> s2 route.
while (!pq.empty()) {
int node = pq.top().second;
int cost = pq.top().first;
pq.pop();
for (int i = 0; i < graph[node].size(); i++) {
int neighbor = graph[node][i].first;
int neighborDist = graph[node][i].second;
if (distance[neighbor] > cost + neighborDist) {
distance[neighbor] = neighborDist + cost;
pq.push({ distance[neighbor], neighbor });
}
}
}
vector<int> distance2(n + 1, INF);
pq.push({ 0, s1 });
distance2[s1] = 0;
// s1 -> s2
while (!pq.empty()) {
int node = pq.top().second;
int cost = pq.top().first;
pq.pop();
for (int i = 0; i < graph[node].size(); i++) {
int neighbor = graph[node][i].first;
int neighborDist = graph[node][i].second;
if (distance2[neighbor] > cost + neighborDist) {
distance2[neighbor] = neighborDist + cost;
pq.push({ distance2[neighbor], neighbor });
}
}
}
vector<int> distance3(n + 1, INF);
pq.push({ 0, s2 });
distance3[s2] = 0;
// s2 -> s1
while (!pq.empty()) {
int node = pq.top().second;
int cost = pq.top().first;
pq.pop();
for (int i = 0; i < graph[node].size(); i++) {
int neighbor = graph[node][i].first;
int neighborDist = graph[node][i].second;
if (distance3[neighbor] > cost + neighborDist) {
distance3[neighbor] = neighborDist + cost;
pq.push({ distance3[neighbor], neighbor });
}
}
}
vector<int> distance4(n + 1, INF);
pq.push({ 0, s1 });
distance4[s1] = 0;
// s1 -> n
while (!pq.empty()) {
int node = pq.top().second;
int cost = pq.top().first;
pq.pop();
for (int i = 0; i < graph[node].size(); i++) {
int neighbor = graph[node][i].first;
int neighborDist = graph[node][i].second;
if (distance4[neighbor] > cost + neighborDist) {
distance4[neighbor] = neighborDist + cost;
pq.push({ distance4[neighbor], neighbor });
}
}
}
vector<int> distance5(n + 1, INF);
pq.push({ 0, s2 });
distance5[s2] = 0;
// s2 -> n
while (!pq.empty()) {
int node = pq.top().second;
int cost = pq.top().first;
pq.pop();
for (int i = 0; i < graph[node].size(); i++) {
int neighbor = graph[node][i].first;
int neighborDist = graph[node][i].second;
if (distance5[neighbor] > cost + neighborDist) {
distance5[neighbor] = neighborDist + cost;
pq.push({ distance5[neighbor], neighbor });
}
}
}
if (distance[s1] == INF || distance2[s2] == INF || distance5[n] == INF || distance[s2] == INF || distance3[s1] == INF || distance4[n] == INF)
cout << -1 << endl;
else
cout << min(distance[s1] + distance2[s2] + distance5[n], distance[s2] + distance3[s1] + distance4[n]);
}
| cs |
댓글
댓글 쓰기