Overview

Find the shortest time to depart from base \(1\), visit base \(T\) at least once, and then return to base \(1\).

Analysis

This problem is not simply about finding a path “base \(1\) → base \(T\) → base \(1\)”, but rather requires finding the shortest path, so a shortest path algorithm such as Dijkstra’s algorithm is needed.

A naive approach would be to exhaustively search all paths, but since the number of vertices \(N\) can be up to \(10^5\) and the number of edges \(M\) can be up to \(2 \times 10^5\), this is not practical (TLE). Additionally, since it is allowed to traverse the same vertex or edge multiple times, searching with DFS or similar methods may result in infinite loops.

The key observation is that we only need to find “the shortest distance from base \(1\) to base \(T\)” and “the shortest distance from base \(T\) to base \(1\)” separately. Since the graph is undirected, these shortest distances are the same, but by computing them separately, we can calculate simply without worrying about intermediate stops.

Therefore, it is sufficient to find the following two shortest distances: - Shortest distance from base \(1\) to base \(T\) - Shortest distance from base \(T\) to base \(1\)

If either one is unreachable, then no path satisfying the conditions exists, so we output -1.

Algorithm

1. Build an undirected graph in adjacency list format.
2. Use Dijkstra’s algorithm to compute the following:
   • dist_from_1[v]: Shortest distance from base \(1\) (for each vertex \(v\))
   • dist_from_T[v]: Shortest distance from base \(T\) (for each vertex \(v\))
3. If both dist_from_1[T] and dist_from_T[1] are finite values, their sum is the answer.
4. If either is infinity (unreachable), output -1.

Complexity

• Time complexity: \(O((N + M) \log N)\)
  • Dijkstra’s algorithm is executed twice. Each run is \(O((N + M) \log N)\).
• Space complexity: \(O(N + M)\)
  • Used for the adjacency list and distance arrays.

Implementation Notes

• Since the graph is undirected, for each input edge \((A_i, B_i)\), add edges in both directions.

• In Dijkstra’s algorithm, using a priority queue (heapq) allows efficiently extracting the vertex with the minimum cost.

• To detect unreachable cases, check whether the distance is inf (infinity).

  Source Code

import heapq
import sys

def dijkstra(n, graph, start):
    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, cost in graph[u]:
            if dist[u] + cost < dist[v]:
                dist[v] = dist[u] + cost
                heapq.heappush(pq, (dist[v], v))
    return dist

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    T = int(data[idx]); idx += 1
    
    graph = [[] for _ in range(N + 1)]
    
    for _ in range(M):
        A = int(data[idx]); idx += 1
        B = int(data[idx]); idx += 1
        C = int(data[idx]); idx += 1
        graph[A].append((B, C))
        graph[B].append((A, C))
    
    dist_from_1 = dijkstra(N, graph, 1)
    dist_from_T = dijkstra(N, graph, T)
    
    if dist_from_1[T] == float('inf') or dist_from_T[1] == float('inf'):
        print(-1)
    else:
        result = dist_from_1[T] + dist_from_T[1]
        print(result)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.