解法
正の重みを持つ無向グラフで、頂点v1とv2の両方を通る最短経路を求めます。必須の2頂点を訪れる順序は1 → v1 → v2 → Nまたは1 → v2 → v1 → Nの2通りだけです。それぞれの区間の最短距離を足した2つの候補から小さい方を選び、どちらの候補も到達不能なら-1を出力します。
始点1、v1、v2からそれぞれダイクストラ法を実行します。1つ目の順序の距離はd(1,v1) + d(v1,v2) + d(v2,N)、2つ目はd(1,v2) + d(v2,v1) + d(v1,N)です。辺は無向なのでd(v1,v2) = d(v2,v1)です。始点または終点が必須頂点と同じ場合も、距離0として自然に処理できます。
距離と候補の合計にはlongを使い、到達不能な区間を含む合計は計算しません。優先度付きキューに残った古い項目は、現在の最短距離と異なれば破棄します。時間計算量はO((V + E) log V)、隣接リストと距離配列を含む空間計算量はO(V + E)です。
Java
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
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;
public class Main {
private static final long INF = Long.MAX_VALUE / 4;
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int n = input.nextInt();
int e = input.nextInt();
List<Edge>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) {
graph[i] = new ArrayList<>();
}
for (int i = 0; i < e; i++) {
int a = input.nextInt() - 1;
int b = input.nextInt() - 1;
long weight = input.nextLong();
graph[a].add(new Edge(b, weight));
graph[b].add(new Edge(a, weight));
}
int v1 = input.nextInt() - 1;
int v2 = input.nextInt() - 1;
long[] fromStart = dijkstra(graph, 0);
long[] fromV1 = dijkstra(graph, v1);
long[] fromV2 = dijkstra(graph, v2);
long viaV1ThenV2 = routeLength(
fromStart[v1], fromV1[v2], fromV2[n - 1]);
long viaV2ThenV1 = routeLength(
fromStart[v2], fromV2[v1], fromV1[n - 1]);
long answer = Math.min(viaV1ThenV2, viaV2ThenV1);
System.out.println(answer == INF ? -1 : answer);
}
private static long[] dijkstra(List<Edge>[] graph, int start) {
long[] distance = new long[graph.length];
Arrays.fill(distance, INF);
distance[start] = 0;
PriorityQueue<State> queue = new PriorityQueue<>();
queue.offer(new State(start, 0));
while (!queue.isEmpty()) {
State current = queue.poll();
if (current.distance != distance[current.vertex]) {
continue;
}
for (Edge edge : graph[current.vertex]) {
long nextDistance = current.distance + edge.weight;
if (nextDistance < distance[edge.to]) {
distance[edge.to] = nextDistance;
queue.offer(new State(edge.to, nextDistance));
}
}
}
return distance;
}
private static long routeLength(long first, long middle, long last) {
if (first == INF || middle == INF || last == INF) {
return INF;
}
return first + middle + last;
}
private static class Edge {
final int to;
final long weight;
Edge(int to, long weight) {
this.to = to;
this.weight = weight;
}
}
private static class State implements Comparable<State> {
final int vertex;
final long distance;
State(int vertex, long distance) {
this.vertex = vertex;
this.distance = distance;
}
@Override
public int compareTo(State other) {
return Long.compare(distance, other.distance);
}
}
private static class FastScanner {
private final BufferedInputStream in = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int index;
private int size;
private int read() throws IOException {
if (index == size) {
size = in.read(buffer);
index = 0;
if (size == -1) {
return -1;
}
}
return buffer[index++];
}
long nextLong() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
long value = 0;
while (c > ' ') {
value = value * 10 + c - '0';
c = read();
}
return value;
}
int nextInt() throws IOException {
return (int) nextLong();
}
}
}