Overview

This is a problem of finding the shortest time to travel from point \(S\) to point \(T\) via point \(G\). The answer is obtained by summing the shortest distance from \(S \to G\) and the shortest distance from \(G \to T\).

Analysis

Takahashi needs to travel in the order \(S \to G \to T\). The key insight here is that the route can be split into two parts at the waypoint \(G\).

• First half: Shortest path from \(S\) to \(G\)
• Second half: Shortest path from \(G\) to \(T\)

Since the problem statement says that the same roads and points may be visited multiple times, there is no issue even if the first and second half routes overlap. In other words, by independently finding the shortest distance for each half and taking their sum, we obtain the optimal solution.

Comparison with a Naive Approach

An approach that “enumerates all paths from \(S\) to \(T\) passing through \(G\)” would be infeasible due to combinatorial explosion. However, with the above decomposition observation, solving the shortest path problem just twice is sufficient.

Algorithm

1. Build the graph as an adjacency list.
2. Using Dijkstra’s algorithm, compute the shortest distances \(\mathrm{dist\_s}\) from source \(S\) to all vertices.
3. Similarly, compute the shortest distances \(\mathrm{dist\_g}\) from source \(G\) to all vertices.
4. The answer is \(\mathrm{dist\_s}[G] + \mathrm{dist\_g}[T]\). However, if either value is \(\infty\) (unreachable), output \(-1\).

Example: When \(S=1, G=3, T=5\), if Dijkstra’s algorithm finds the shortest distance from \(1\) to \(3\) is \(4\) and the shortest distance from \(3\) to \(5\) is \(7\), then the answer is \(4 + 7 = 11\).

Why Two Runs of Dijkstra’s Algorithm Suffice

A single run of Dijkstra’s algorithm from source \(G\) gives us the shortest distance \(G \to T\). A single run of Dijkstra’s algorithm from source \(S\) gives us the shortest distance \(S \to G\). With a total of two runs of Dijkstra’s algorithm, all the necessary information is obtained.

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Since Dijkstra’s algorithm is run twice, it is \(O(2 \times (N + M) \log N)\), but ignoring constant factors, it is \(O((N + M) \log N)\).
• Space complexity: \(O(N + M)\)
  • \(O(N + M)\) is used for the graph’s adjacency list, and \(O(N)\) for the distance arrays.

Implementation Notes

• Fast input: By reading all input at once with sys.stdin.buffer.read(), splitting, and processing, it runs sufficiently fast even in Python.

• Unreachability check: If a distance remains float('inf'), the destination is deemed unreachable and \(-1\) is output.

• Edge costs can be up to \(10^9\) and the number of vertices up to \(10^5\), so the sum of shortest distances can be on the order of \(10^{14}\). In Python there is no concern about integer overflow, but in other languages, a 64-bit integer type must be used.

• The graph is bidirectional (undirected), so for each edge, both directions must be added to the adjacency list.

  Source Code

import heapq
import sys

def dijkstra(graph, start, n):
    dist = [float('inf')] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > dist[u]:
            continue
        for v, w in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(pq, (dist[v], v))
    return dist

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    S = int(input_data[idx]); idx += 1
    G = int(input_data[idx]); idx += 1
    T = int(input_data[idx]); idx += 1

    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u = int(input_data[idx]); idx += 1
        v = int(input_data[idx]); idx += 1
        c = int(input_data[idx]); idx += 1
        graph[u].append((v, c))
        graph[v].append((u, c))

    dist_s = dijkstra(graph, S, N)
    dist_g = dijkstra(graph, G, N)

    sg = dist_s[G]
    gt = dist_g[T]

    if sg == float('inf') or gt == float('inf'):
        print(-1)
    else:
        print(sg + gt)

main()

This editorial was generated by claude4.6opus-thinking.