[Link] https://www.acmicpc.net/problem/1504
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
//Edge Case: Vertext that must to be included could be start or end point(line 71)
import java.util.*;
import java.io.*;
public class Main {
static int NUM = 1000000007;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
String[] line = br.readLine().split(" ");
int n = toi(line[0]), e = toi(line[1]);
Result[] tmp;
ArrayList<ArrayList<Distance>> al = new ArrayList<>();
for(int i = 0; i < n; i++) al.add(new ArrayList<>());
for(int i = 0; i < e; i++) {
line = br.readLine().split(" ");
int a = toi(line[0]), b = toi(line[1]), c = toi(line[2]);
al.get(a - 1).add(new Distance(b - 1, c));
al.get(b - 1).add(new Distance(a - 1, c));
}
line = br.readLine().split(" ");
int v1 = toi(line[0]) - 1, v2 = toi(line[1]) - 1;
Result start_v1, start_v2, v1_v2, v1_end, v2_end;
tmp = dijkstra(al, 0, new int[] { v1, v2 });
start_v1 = tmp[0];
start_v2 = tmp[1];
tmp = dijkstra(al, n - 1, new int[] { v1, v2 });
v1_end = tmp[0];
v2_end = tmp[1];
tmp = dijkstra(al, v1, new int[] { v2 });
v1_v2 = tmp[0];
int len1 = 0, len2 = 0;
if(!v1_v2.visit) {
print(-1);
} else if(start_v1.visit && v2_end.visit) {
if(start_v2.visit && v1_end.visit) print(Math.min(start_v1.dis + v1_v2.dis + v2_end.dis, start_v2.dis + v1_v2.dis + v1_end.dis));
else print(start_v1.dis + v1_v2.dis + v2_end.dis);
} else {
if(start_v2.visit && v1_end.visit) print(start_v2.dis + v1_v2.dis + v1_end.dis);
else print(-1);
}
}
static Result[] dijkstra(ArrayList<ArrayList<Distance>> al, int vertext, int[] dest) {
int[] dis = new int[al.size()];
Arrays.fill(dis, Integer.MAX_VALUE);
dis[vertext] = 0;
boolean[] visit = new boolean[al.size()];
visit[vertext] = true;
PriorityQueue<int[]> pq = new PriorityQueue<>((l, r) -> l[1] - r[1]);
for(Distance d: al.get(vertext)) {
pq.add(new int[] { d.dest, d.dis });
dis[d.dest] = d.dis;
}
while(!pq.isEmpty()) {
int[] bottom = pq.poll();
if(visit[bottom[0]]) continue;
visit[bottom[0]] = true;
for(Distance d: al.get(bottom[0])) {
if(visit[d.dest]) continue;
dis[d.dest] = Math.min(dis[d.dest], dis[bottom[0]] + d.dis);
pq.add(new int[] { d.dest, dis[d.dest]});
}
}
Result[] ans = new Result[dest.length];
for(int i = 0; i < dest.length; i++) {
ans[i] = new Result(dis[dest[i]], visit[dest[i]]);
}
return ans;
}
static class Distance {
int dest;
int dis;
public Distance(int dest, int dis) { this.dest = dest; this.dis = dis; }
}
static class Result {
int dis;
boolean visit;
public Result(int dis, boolean visit) { this.dis = dis; this.visit = visit; }
}
static int toi(String s) { return Integer.parseInt(s); }
static <T> void print(T s) { System.out.print(s); }
static <T> void println(T s) { System.out.println(s); }
}