9370 - 미확인 도착지
본문
(취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 $s$지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익)
어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다행히도 당신은 후각이 개만큼 뛰어나다. 이 후각으로 그들이 $g$와 $h$ 교차로 사이에 있는 도로를 지나갔다는 것을 알아냈다.
이 듀오는 대체 어디로 가고 있는 것일까?
예제 입력의 두 번째 케이스를 시각화한 것이다. 이 듀오는 회색 원에서 두 검은 원 중 하나로 가고 있고 점선으로 표시된 도로에서 냄새를 맡았다. 따라서 그들은 $6$으로 향하고 있다.
입력
첫 번째 줄에는 테스트 케이스의 $T$($1 \leq T \leq 100$)가 주어진다. 각 테스트 케이스마다
- 첫 번째 줄에 3개의 정수 $n$, $m$, $t$ ($2 \leq n \leq 2000$, $1 \leq m \leq 50000$ and $1 \leq t \leq 100$)가 주어진다. 각각 교차로, 도로, 목적지 후보의 개수이다.
- 두 번째 줄에 3개의 정수 $s$, $g$, $h$ ($1 \leq s, g, h \leq n$)가 주어진다. $s$는 예술가들의 출발지이고, $g$, $h$는 문제 설명에 나와 있다. ($g \neq h$)
- 그 다음 $m$개의 각 줄마다 3개의 정수 $a, b, d$ ($1 \leq a < b \leq n$ and $1 \leq d \leq 1000$)가 주어진다. $a$와 $b$ 사이에 길이 $d$의 양방향 도로가 있다는 뜻이다.
- 그 다음 $t$개의 각 줄마다 정수 $x$가 주어지는데, $t$개의 목적지 후보들을 의미한다. 이 $t$개의 지점들은 서로 다른 위치이며 모두 $s$와 같지 않다.
교차로 사이에는 도로가 많아봐야 1개이다. $m$개의 줄 중에서 $g$와 $h$ 사이의 도로를 나타낸 것이 존재한다. 또한 이 도로는 목적지 후보들 중 적어도 1개로 향하는 최단 경로의 일부이다.
출력
테스트 케이스마다
- 입력에서 주어진 목적지 후보들 중 불가능한 경우들을 제외한 목적지들을 공백으로 분리시킨 오름차순의 정수들로 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 3sec | 256MB |
풀이
최단경로를 찾는데, 우리가 원하는 경로를 지나갔는가를 판단하는 문제이다. 일단 타겟으로 주어지는 모든 점들에 대해 최단경로를 찾아야하는데, 시작지점이 딱 하나로 정해지므로 다익스트라 알고리즘을 통해 계산하는 것이 좋을 것이라고 짐작할 수 있다. 그래서 시작점으로부터 모든 점들에 대한 다익스트라를 실행하는 것을 기본 방법으로 생각하자.
다만, 그냥 다익스트라를 통해 최단경로를 구한다고 되는 문제는 아니다. 최단경로가 특정한 경로를 포함하는지를 판단해야한다. 다익스트라 알고리즘은 어떠한 경로를 지났는지도 확인할 수는 있으니까, 약간의 조절을 통해 되추적을 진행해도 된다.
문제는, “가중치가 같은 다른 경로로 진행을 먼저 한 경우“가 될 것이다. 알고리즘상 가중치가 적은 방향으로 계속해서 업데이트를 할 것인데, 가중치가 같은 다른 방법으로 진행을 해버리면 ‘특정한 경로’를 지나는 방법에 대한 업데이트가 되지 않을 수 있다. 이를 해결하기 위해서는 다익스트라 알고리즘을 여러번 돌려서 task를 나누는 방법을 사용할 수 있다. 대충 적어보면 아래와 같을 것이다.
- 일단 모든 정점에 대한 최단경로는 구해야하니까 s를 시작점으로 하는 다익스트라를 돌린다 (1)
- 2가지 case를 고려한 경우를 계산한다 (2)
- s -> g -> h -> target : s->g까지 다익스트라, h->target으로 다익스트라
- s -> h -> g -> target : s->h까지 다익스트라, g->target으로 다익스트라
- (1), (2)의 경우를 비교하여 값이 같은 target 정점들은 정답으로 출력한다
이러면 다익스트라 5번만 돌리면 정답을 찾을 수 있다. 근데 귀찮다. 다익스트라 5번 돌리지 말고, 이걸 1번만에 해결할 수 있는 방법이 없을까?
다익스트라 알고리즘이 s로부터 다른 정점들로 가는 최단경로 가중치를 기록하는데, 이 값을 이용해서 최단경로가 특정한 길을 지났다고 인식하고 싶다. 그렇다면, 다른 정점들이 절대로 가질 수 없는 값을 가지도록 하면 될 것이다. 가중치들이 전부 자연수로 주어지니까, 특정한 길의 가중치를 소수로 지정해버리면 이 조건을 만들어낼 수 있다. 그리고 가중치가 같은 경로들 중에서도 특정한 길에 대한 계산을 먼저 하고 싶기 때문에, 특정한 길의 가중치 값을 기존의 값보다 작게 하면 된다. 즉, 0.1 빼주면 전처리를 할 수 있다. 우리는 s로부터 다익스트라를 1번 돌려서, 최단경로가 소수가 나왔다면 그 점은 특정한 길을 지났다고 판별할 수 있게 된다!
다만 필자는 C로 문제를 풀기 때문에 소수 혐오증에 빠져있어, 소수로 구현하지 않고 홀짝으로 구분한다. 입력으로 주어지는 모든 길의 가중치에 $\times 2$ 해주고, 특정한 길의 가중치를 $1$ 빼주는 것으로 구현하였다.
여담으로, 최종 수정일 (2023 / 2 / 23) 에 기존에 cpp로 제출했던 문제를 다시 c로 재구현을 진행했는데, 계속해서 틀렸습니다를 받았다. 알고리즘이 다 똑같은데 왜 맞왜틀하나 싶었는데, 힙의 길이가 문제였다. 같은 정점을 visit 체크 안하고 계속해서 힙에 넣으니까, 힙의 길이가 최대 $\frac{n \times (n+1)}{2}$가 되어야했다. 안일하게 $2n$ 했더니 틀리더라. 문제를 최대한 악랄하게 주면 힙의 길이가 저정도 되어야하겠지만, 다행히도 $4n$의 길이로 주니까 풀리긴 하더라.
코드
사용 언어 : C
최종 수정일 : 2023 / 2 / 23
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
#include <stdio.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
typedef struct Node {
int idx, dis, pre;
} ND;
#define INF (987654321 * 2)
#define MAX_IDX (2000 + 1)
#define NONE 0
int matrix[MAX_IDX][MAX_IDX];
int dist[MAX_IDX];
bool target[MAX_IDX + 1];
int n, m, t;
int s, g, h;
ND heap[4 * MAX_IDX + 10];
int top;
void init() {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
matrix[i][j] = INF;
}
dist[i] = INF;
target[i] = false;
}
top = 0;
return;
}
#define min(a, b) (((a) > (b)) ? (b) : (a))
void push(ND x) {
heap[++top] = x;
int i = top;
while (i > 1 && x.dis < heap[i / 2].dis) {
ND a = heap[i / 2];
heap[i / 2] = x, heap[i] = a;
i /= 2;
}
return;
}
ND pop() {
if (top == 0) {
return (ND){NONE, INF, NONE};
}
ND retval = heap[1];
heap[1] = heap[top--];
int i = 1, tp = 2;
while (tp < top) {
if (heap[tp].dis > heap[tp + 1].dis) {
++tp;
}
if (heap[i].dis <= heap[tp].dis) {
break;
}
ND a = heap[tp];
heap[tp] = heap[i], heap[i] = a;
i = tp, tp *= 2;
}
if (tp == top && heap[i].dis > heap[tp].dis) {
ND a = heap[tp];
heap[tp] = heap[i], heap[i] = a;
}
return retval;
}
void dijkstra() {
for (int i = 1; i <= n; ++i) {
push((ND){i, dist[i], NONE});
}
while (top > 0) {
ND node = pop();
if (dist[node.idx] < node.dis) {
continue;
}
for (int i = 1; i <= n; ++i) {
if (matrix[node.idx][i] != INF) {
if (dist[i] > dist[node.idx] + matrix[node.idx][i]) {
dist[i] = dist[node.idx] + matrix[node.idx][i];
push((ND){i, dist[i], node.idx});
}
}
}
}
return;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
scanf("%d %d %d", &n, &m, &t);
init();
scanf("%d %d %d", &s, &g, &h);
while (m--) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
matrix[a][b] = matrix[b][a] = 2 * c;
}
--matrix[g][h], --matrix[h][g];
while (t--) {
int a;
scanf("%d", &a);
target[a] = true;
}
dist[s] = 0;
dijkstra();
for (int i = 1; i <= n; ++i) {
if (target[i] == true && dist[i] % 2 == 1) {
printf("%d ", i);
}
}
printf("\n");
}
return 0;
}