On this page
Approach
For each test case, run Dijkstra from the source s and from both endpoints g and h of the designated edge. A candidate destination x qualifies exactly when some shortest route from s to x can use that edge. Its shortest distance must therefore equal one of these two route lengths:
dist(s, g) + w(g, h) + dist(h, x)dist(s, h) + w(g, h) + dist(g, x)
The two expressions cover both directions of travel across the undirected g-h edge. If several parallel edges connect g and h, use their minimum weight: any heavier parallel edge cannot make a shortest route, while the minimum one is available in the graph. An unreachable segment makes that expression invalid, so check for INF before adding distances.
For correctness, if a shortest route uses g-h, its prefix to the first endpoint and suffix from the other endpoint must themselves be shortest; otherwise replacing either part would produce a shorter route. Its total length is therefore one of the two expressions above. Conversely, if either expression equals dist(s, x), concatenating those shortest segments with the g-h edge gives a shortest route that uses the edge.
The graph is stored as an adjacency list, and Dijkstra uses a min-priority queue with lazy deletion. Distances and edge weights are long; Long.compare orders queue entries without subtraction overflow. Candidates are sorted numerically before output. The time complexity per test case is O((V + E) log V + C log C), where C is the number of candidates; space complexity is O(V + E).
Java
import java.io.BufferedInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
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 testCases = input.nextInt();
StringBuilder output = new StringBuilder();
for (int testCase = 0; testCase < testCases; testCase++) {
int n = input.nextInt();
int m = input.nextInt();
int candidateCount = input.nextInt();
int source = input.nextInt() - 1;
int g = input.nextInt() - 1;
int h = input.nextInt() - 1;
List<Edge>[] graph = new ArrayList[n];
for (int vertex = 0; vertex < n; vertex++) {
graph[vertex] = new ArrayList<>();
}
long ghWeight = INF;
for (int i = 0; i < m; 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));
if ((a == g && b == h) || (a == h && b == g)) {
ghWeight = Math.min(ghWeight, weight);
}
}
long[] fromSource = dijkstra(graph, source);
long[] fromG = dijkstra(graph, g);
long[] fromH = dijkstra(graph, h);
List<Integer> candidates = new ArrayList<>(candidateCount);
for (int i = 0; i < candidateCount; i++) {
int candidate = input.nextInt() - 1;
long shortest = fromSource[candidate];
if (shortest != INF
&& ghWeight != INF
&& (equalsRoute(shortest, fromSource[g], ghWeight, fromH[candidate])
|| equalsRoute(shortest, fromSource[h], ghWeight, fromG[candidate]))) {
candidates.add(candidate + 1);
}
}
Collections.sort(candidates);
for (int candidate : candidates) {
output.append(candidate).append(' ');
}
output.append('\n');
}
System.out.print(output);
}
private static boolean equalsRoute(long shortest, long first, long edge, long last) {
return first != INF && edge != INF && last != INF
&& shortest == first + edge + last;
}
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<>(
(left, right) -> Long.compare(left.distance, right.distance));
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 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;
}
}
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++];
}
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();
}
}
}