Overview

This is a constrained shortest path problem: “go from \(S\) to \(G\), then go to \(T\).” Since the graph is a weighted undirected graph, running Dijkstra’s algorithm once from vertex \(G\) gives us the answer as \(dist(G,S) + dist(G,T)\).

Analysis

First, Takahashi’s movement can always be split into two stages:

1. Go from \(S\) to \(G\)
2. Go from \(G\) to \(T\)

The key insight here is that the minimum time is the sum of these two shortest distances.

This is because any valid path can be decomposed into:

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

The length of the first half is at least the shortest distance from \(S\) to \(G\), and the length of the second half is at least the shortest distance from \(G\) to \(T\).

Therefore, the total length of any path is at least

\(dist(S,G) + dist(G,T)\)

On the other hand, we can achieve exactly this length by concatenating the shortest path from \(S \to G\) with the shortest path from \(G \to T\). Thus, the answer is

\(dist(S,G) + dist(G,T)\)

---

Why the naive approach doesn’t work

If we try to enumerate all paths from \(S\) to \(T\) passing through \(G\), the number of paths is extremely large, making it completely infeasible.

Additionally, since edge weights \(C_i\) can be as large as \(10^9\), plain BFS cannot be used. Since we need shortest distances in a weighted graph, the standard approach is to use Dijkstra’s algorithm.

---

A further important observation

Normally, we could compute:

• Shortest distances from \(S\) to all vertices
• Shortest distances from \(G\) to all vertices

and then compute the answer as \(dist_S[G] + dist_G[T]\).

However, since the graph in this problem is an undirected graph,

\(dist(S,G) = dist(G,S)\)

holds. Therefore, running Dijkstra’s algorithm just once from \(G\) is sufficient.

This gives us both:

• \(dist[G \to S]\)
• \(dist[G \to T]\)

and the answer is their sum.

Algorithm

1. Build the undirected graph using an adjacency list.
2. Run Dijkstra’s algorithm with vertex \(G\) as the source.
3. Check \(dist[S]\) and \(dist[T]\).
   • If either is unreachable, output \(-1\)
   • Otherwise, output \(dist[S] + dist[T]\)

---

Flow of Dijkstra’s Algorithm

• Insert pairs of (distance, vertex) into a priority queue
• Process the vertex with the currently smallest distance first
• Update distances of adjacent vertices using edges

In this code, we terminate early once the shortest distances to both \(S\) and \(T\) have been finalized. Since we only need the distances to these two vertices, this provides a slight efficiency improvement.

Complexity

• Time complexity: \(O((N+M)\log N)\)
• Space complexity: \(O(N+M)\)

Implementation Notes

• Vertex numbers are \(1\)-indexed in the input, so they are converted to \(0\)-indexed in the code.
• In Dijkstra’s algorithm, the same vertex may be inserted into the priority queue multiple times. Therefore, if d != dist[v]: continue is used to ignore outdated entries.
• Unreachability is determined by checking whether the distance array still holds the value INF.
• Since edge weights can be large, INF is set to a sufficiently large value (\(10^{30}\) in this code).

For example, if:

• \(dist(G,S)=5\)
• \(dist(G,T)=7\)

then the minimum time is \(5+7=12\). Although you are allowed to pass through the same vertices or edges multiple times along the way, when minimizing the total time, this sum is always optimal.

Source Code

import sys
import heapq

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return

    it = iter(data)
    N = next(it)
    M = next(it)
    S = next(it) - 1
    G = next(it) - 1
    T = next(it) - 1

    graph = [[] for _ in range(N)]
    for _ in range(M):
        u = next(it) - 1
        v = next(it) - 1
        c = next(it)
        graph[u].append((v, c))
        graph[v].append((u, c))

    INF = 10**30
    dist = [INF] * N
    dist[G] = 0
    hq = [(0, G)]
    need = 2  # S and T
    found_s = (G == S)
    found_t = (G == T)

    while hq:
        d, v = heapq.heappop(hq)
        if d != dist[v]:
            continue

        if v == S and not found_s:
            found_s = True
            need -= 1
        if v == T and not found_t:
            found_t = True
            need -= 1
        if need == 0:
            break

        for nv, w in graph[v]:
            nd = d + w
            if nd < dist[nv]:
                dist[nv] = nd
                heapq.heappush(hq, (nd, nv))

    if dist[S] >= INF or dist[T] >= INF:
        print(-1)
    else:
        print(dist[S] + dist[T])

if __name__ == "__main__":
    main()

---

This editorial was generated by gpt-5.4-high.