Overview

This is a problem of finding the “shortest time to travel in the order \(S \rightarrow G \rightarrow T\).”
Since the graph is a weighted undirected graph, the basic approach is to use Dijkstra’s algorithm for shortest path computation.

Analysis

The key point is that the waypoint \(G\) is mandatory.
The shortest path with this condition can be split into two parts:

1. The shortest distance from \(S\) to \(G\)
2. The shortest distance from \(G\) to \(T\)

The overall shortest time is the sum of these: [ \text{dist}(S,G) + \text{dist}(G,T) ]

The reason this works is that if the entire path has the form \(S \to \cdots \to G \to \cdots \to T\), then the first half and the second half can be minimized independently.
If the first half were not the shortest, we could replace it with a shorter first half to reduce the overall distance, contradicting the assumption of it being the shortest. The same argument applies to the second half.

If we naively try to “search all paths from \(S\) that pass through \(G\) and reach \(T\),” the number of paths becomes enormous and impractical (it can grow exponentially).
Also, since the graph is weighted, BFS cannot produce correct shortest distances (BFS is only valid when all edge weights are the same).

Therefore, we use Dijkstra’s algorithm, which is well-suited for shortest paths with non-negative weights.
We only need to run it twice: once from \(S\) and once from \(G\).

Algorithm

1. Build an undirected graph using an adjacency list.
2. Run Dijkstra’s algorithm from \(S\) to obtain distS (shortest distances to each vertex).
3. Run Dijkstra’s algorithm from \(G\) to obtain distG.
4. If distS[G] or distG[T] is unreachable (INF), output -1.
5. Otherwise, output distS[G] + distG[T].

The if d != dist[v]: continue in the code is a standard technique for discarding outdated (unnecessary) entries remaining in the priority queue.

Complexity

• Time complexity: \(O((N+M)\log N)\) executed twice, so excluding constant factors, \(O((N+M)\log N)\)
• Space complexity: \(O(N+M)\) (graph + distance arrays + priority queue)

Implementation Notes

• Distances can become very large, so use a sufficiently large value like INF = 10**30.

• Since vertex numbers are \(1\)-indexed, set the array size to N+1.

• Don’t forget to check for unreachability (distS[G] >= INF or distG[T] >= INF).

  Source Code

import sys
import heapq

def dijkstra(start, graph, n):
    INF = 10**30
    dist = [INF] * (n + 1)
    dist[start] = 0
    pq = [(0, start)]
    while pq:
        d, v = heapq.heappop(pq)
        if d != dist[v]:
            continue
        for to, w in graph[v]:
            nd = d + w
            if nd < dist[to]:
                dist[to] = nd
                heapq.heappush(pq, (nd, to))
    return dist

def main():
    input = sys.stdin.readline
    N, M, S, G, T = map(int, input().split())
    graph = [[] for _ in range(N + 1)]
    for _ in range(M):
        u, v, c = map(int, input().split())
        graph[u].append((v, c))
        graph[v].append((u, c))

    distS = dijkstra(S, graph, N)
    distG = dijkstra(G, graph, N)

    INF = 10**30
    if distS[G] >= INF or distG[T] >= INF:
        print(-1)
    else:
        print(distS[G] + distG[T])

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.3-codex.