For each vertex i, the answer is the shortest distance from vertex 1 to i plus the shortest distance from i to vertex N. The graph is undirected, so the second distance equals the shortest distance from N to i. Run Dijkstra’s algorithm once from vertex 1 and once from vertex N, then add the two distances for every vertex.
Store each edge in an adjacency list. Dijkstra’s algorithm is valid because all edge weights are nonnegative; with negative weights, settling the currently closest vertex is not safe. The priority queue may contain outdated entries, so discard an entry when its distance no longer matches the distance array. Keep weights and distances as long. INF marks an unreachable vertex, and the program prints -1 if either search cannot reach a vertex. Before relaxing an edge, it checks that adding the weight stays below INF, avoiding overflow and preserving the unreachable sentinel.
Each run takes O((N + M) log N) time with a priority queue and adjacency lists. Running it twice does not change the asymptotic bound. The graph and the two distance arrays use O(N + M) space.
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
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;
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 {
final int vertex;
final long distance;
State(int vertex, long distance) {
this.vertex = vertex;
this.distance = distance;
}
}
public static void main(String[] args) throws IOException {
FastScanner input = new FastScanner();
int vertexCount = input.nextInt();
int edgeCount = input.nextInt();
List<List<Edge>> graph = new ArrayList<>(vertexCount);
for (int vertex = 0; vertex < vertexCount; vertex++) {
graph.add(new ArrayList<>());
}
for (int i = 0; i < edgeCount; i++) {
int a = input.nextInt() - 1;
int b = input.nextInt() - 1;
long weight = input.nextLong();
graph.get(a).add(new Edge(b, weight));
graph.get(b).add(new Edge(a, weight));
}
long[] fromStart = dijkstra(graph, 0);
long[] fromGoal = dijkstra(graph, vertexCount - 1);
StringBuilder output = new StringBuilder();
for (int vertex = 0; vertex < vertexCount; vertex++) {
if (fromStart[vertex] == INF || fromGoal[vertex] == INF) {
output.append(-1);
} else {
output.append(fromStart[vertex] + fromGoal[vertex]);
}
output.append('\n');
}
System.out.print(output);
}
private static long[] dijkstra(List<List<Edge>> graph, int source) {
long[] distance = new long[graph.size()];
Arrays.fill(distance, INF);
distance[source] = 0;
PriorityQueue<State> queue = new PriorityQueue<>(
(left, right) -> Long.compare(left.distance, right.distance));
queue.add(new State(source, 0));
while (!queue.isEmpty()) {
State current = queue.poll();
if (current.distance != distance[current.vertex]) {
continue;
}
for (Edge edge : graph.get(current.vertex)) {
if (edge.weight >= INF - current.distance) {
continue;
}
long candidate = current.distance + edge.weight;
if (candidate < distance[edge.to]) {
distance[edge.to] = candidate;
queue.add(new State(edge.to, candidate));
}
}
}
return distance;
}
private static class FastScanner {
private final BufferedInputStream input = new BufferedInputStream(System.in);
private final byte[] buffer = new byte[1 << 16];
private int position;
private int length;
private int read() throws IOException {
if (position == length) {
length = input.read(buffer);
position = 0;
if (length == -1) {
return -1;
}
}
return buffer[position++];
}
private 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;
}
private int nextInt() throws IOException {
return (int) nextLong();
}
}
}