[Link] https://www.acmicpc.net/problem/9370
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
//Edge case s == (g or h) or (g or h) == destination
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String[] line;
int T = toi(br.readLine());
for(int i = 0; i < T; i++) {
line = getLine(br);
int n = toi(line[0]), m = toi(line[1]), t = toi(line[2]);
int[][] dis = new int[n][n];
long[] dijkOrig = new long[n];
long[] dijk1 = new long[n];
long[] dijk2 = new long[n];
Arrays.fill(dijkOrig, Long.MAX_VALUE);
Arrays.fill(dijk1, Long.MAX_VALUE);
Arrays.fill(dijk2, Long.MAX_VALUE);
line = getLine(br);
int s = toi(line[0]), g = toi(line[1]), h = toi(line[2]);
dijkOrig[s - 1] = dijk1[g - 1] = dijk2[h - 1] = 0l;
for(int j = 0; j < m; j++) {
line = getLine(br);
int a = toi(line[0]), b = toi(line[1]), d = toi(line[2]);
dis[a - 1][b - 1] = dis[b - 1][a - 1] = d;
}
dijkstra(dis, dijkOrig, s - 1);
dijkstra(dis, dijk1, g - 1);
dijkstra(dis, dijk2, h - 1);
ArrayList<Integer> ans = new ArrayList<>();
for(int j = 0; j < t; j++) {
int cand = toi(br.readLine());
if(dijkOrig[cand - 1] == (dijkOrig[g - 1] + dis[g-1][h-1] + dijk2[cand - 1])
|| dijkOrig[cand - 1] == (dijkOrig[h - 1] + dis[g-1][h-1] + dijk1[cand - 1])) ans.add(cand);
}
ans.sort((l, r) -> l - r);
for(int e: ans) sb.append(e + " ");
sb.append("\n");
}
print(sb);
}
static void dijkstra(int[][] dis, long[] dijk, int basis) {
boolean[] visit = new boolean[dijk.length];
PriorityQueue<DIJK> pq = new PriorityQueue<>((l, r) -> (int)(l.dis - r.dis));
for(int i = 0; i < dis.length; i++)
if(dis[basis][i] !=0 ) pq.add(new DIJK((long)dis[basis][i], i));
visit[basis] = true;
while(!pq.isEmpty()) {
DIJK bottom = pq.poll();
if(visit[bottom.idx]) continue;
dijk[bottom.idx] = bottom.dis;
visit[bottom.idx] = true;
for(int i = 0; i < dis.length; i++)
if(!visit[i] && dis[bottom.idx][i] != 0 && (bottom.dis + dis[bottom.idx][i] < dijk[i])) {
pq.add(new DIJK((long)bottom.dis + dis[bottom.idx][i], i));
}
}
}
static class DIJK{
long dis;
int idx;
public DIJK(long dis, int idx) { this.dis = dis; this.idx = idx; }
}
static int toi(String s) { return Integer.parseInt(s); }
static String[] getLine(BufferedReader br) throws IOException { return br.readLine().split(" "); }
static <T> void print(T s) { System.out.print(s); }
static <T> void println(T s) { System.out.println(s); }
}