BOJ. Shortest path with specification (1504)

[Link] https://www.acmicpc.net/problem/1504

Approach

In an undirected graph with positive edge weights, find the shortest route from vertex 1 to vertex N that visits both required vertices v1 and v2. There are only two possible orders: 1 → v1 → v2 → N and 1 → v2 → v1 → N. Add the shortest distance for each segment in both orders, then choose the smaller reachable route. If neither route is reachable, print -1.

Run Dijkstra’s algorithm from vertex 1, v1, and v2. The two candidate lengths are d(1,v1) + d(v1,v2) + d(v2,N) and d(1,v2) + d(v2,v1) + d(v1,N). Because the graph is undirected, d(v1,v2) = d(v2,v1). If a required vertex is the start or end, the corresponding segment naturally has distance zero.

Use long for distances and candidate sums, and do not add a candidate if any segment is unreachable. Dijkstra discards stale priority-queue entries when their distance no longer matches the best known distance. The time complexity is O((V + E) log V) and the 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.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();
        }
    }
}