Overview

Starting from base \(1\), we visit base \(T\) and return to headquarters (base \(1\)), solving for the shortest time as a shortest path problem.

Analysis

What we want to find in this problem is the minimum cost of a route [ 1 \to (\text{some bases}) \to T \to (\text{some bases}) \to 1 ] The roads are undirected, the travel time \(C_i\) is the same in both directions, and since \(C_i \ge 1\), all costs are non-negative.

The key observations here are the following two points:

• The “part going from \(1\) to \(T\)” and the “part returning from \(T\) to \(1\)” can each be independently minimized.
  This is because all edge weights are non-negative, so there is no benefit to taking detours (the shortest path portion can always be replaced with the actual shortest path).
• Since the graph is undirected, [ \text{dist}(1, T) = \text{dist}(T, 1) ] holds (because traversing the shortest path from \(1 \to T\) in reverse gives a path from \(T \to 1\)).

Therefore, the answer is [ \text{dist}(1, T) + \text{dist}(T, 1) = 2 \times \text{dist}(1, T) ]

Naively enumerating all paths “starting from \(1\), passing through \(T\), and returning” would result in an enormous (exponential) number of paths and would never finish in time. Also, since we need to find shortest paths, using BFS on a weighted graph would result in WA.

Therefore, we use Dijkstra’s algorithm, the standard approach for weighted shortest paths, to compute the shortest distances from \(1\). If \(T\) is unreachable, we output -1; otherwise, we output \(2 \times \text{dist}(1, T)\).

Algorithm

1. Build an undirected graph using an adjacency list.
2. Use Dijkstra’s algorithm to find the shortest distance dist from source \(1\) to each vertex.
3. If dist[T] is infinity (unreachable), output -1.
4. If reachable, output 2 * dist[T].

Overview of Dijkstra’s algorithm: - Initialize dist[1]=0, and all others to a sufficiently large value (INF). - Using a priority queue, extract the vertex with the smallest distance among those whose shortest distance has not yet been finalized, and relax (update distances) along the edges extending from it.

Complexity

• Time complexity: \(O((N+M)\log N)\) (Dijkstra’s algorithm using a priority queue)
• Space complexity: \(O(N+M)\) (adjacency list and distance array)

Implementation Notes

• Since edge weights \(C_i\) can be up to \(10^9\) and path lengths can become very large, set INF to a sufficiently large value such as \(10^{30}\).

• Since the input size is large, use sys.stdin.buffer.read() for fast input.

• In Dijkstra’s algorithm, when the distance d extracted from the priority queue does not match dist[v] (outdated information), the standard practice is to skip it.

  Source Code

import sys
import heapq

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

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    it = iter(data)
    N = next(it)
    M = next(it)
    T = next(it)

    g = [[] for _ in range(N + 1)]
    for _ in range(M):
        a = next(it); b = next(it); c = next(it)
        g[a].append((b, c))
        g[b].append((a, c))

    dist = dijkstra(N, g, 1)
    if dist[T] >= 10**30:
        print(-1)
    else:
        print(dist[T] * 2)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.