Overview

This problem asks for the minimum time to travel from base 1 to base T and return. The round-trip path can be calculated as “shortest one-way path × 2”.

Analysis

Key Insight

The key point of this problem is the “round-trip” aspect.

• Outbound: Shortest path from base 1 → base T
• Return: Shortest path from base T → base 1

Since roads can be traversed in both directions with the same travel time, the “shortest outbound distance” and “shortest return distance” are equal.

Concrete Example

Consider the following graph:

Base 1 ---(5 min)--- Base 2 ---(3 min)--- Base 3 (T)

• Shortest distance 1 → 3: 5 + 3 = 8 min
• Shortest distance 3 → 1: 3 + 5 = 8 min (traversing the same path in reverse)
• Minimum round-trip time: 8 × 2 = 16 min

Why We Don’t Need to Consider Different Paths for Outbound and Return

In an undirected graph, the shortest distance between any two points is the same in both directions. Therefore, even if different paths were taken for the outbound and return trips, the total time would not be shorter. Taking the shortest path for the round-trip is the optimal solution.

Algorithm

1. Graph Construction: Build the graph in adjacency list format from the input
2. Dijkstra’s Algorithm: Calculate the shortest distances from base 1 to all vertices
3. Answer Calculation:
   • Get the shortest distance \(d\) from base 1 to base T
   • If \(d\) is infinity (unreachable), output -1
   • Otherwise, output \(2 \times d\)

How Dijkstra’s Algorithm Works

Dijkstra’s algorithm efficiently finds the shortest distance from a starting point to all vertices.

1. Initialize the distance to the starting point as 0, and all other vertices as ∞
2. Use a priority queue (min-heap) to process vertices in order of minimum distance
3. Update the distance when moving from each vertex to adjacent vertices (if shorter)
4. Repeat until all vertices are processed

Complexity

• Time Complexity: \(O((N + M) \log N)\)

  • This is the complexity of Dijkstra’s algorithm
  • Each vertex is processed at most once, and for each edge, priority queue operations (\(O(\log N)\)) are performed

• Space Complexity: \(O(N + M)\)

  • Graph adjacency list: \(O(M)\)
  • Distance array: \(O(N)\)
  • Priority queue: at most \(O(M)\)

Implementation Notes

1. Overflow Prevention: Use float('inf') as the initial distance value to represent unreachable states

2. Skipping Already Visited Vertices:

   if d > dist[u]:
      continue
   

   Since the same vertex may be added to the queue multiple times, skip outdated information

3. Handling 1-indexed Input:

   dist = [float('inf')] * (n + 1)
   

   Since base numbers start from 1, the array size is set to \(N+1\)

4. Detecting Unreachable Cases: Use dist_1_to_T == float('inf') to detect when base T is unreachable, and output -1

Source Code

import heapq
from collections import defaultdict

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():
    N, M, T = map(int, input().split())
    
    graph = defaultdict(list)
    for _ in range(M):
        a, b, c = map(int, input().split())
        graph[a].append((b, c))
        graph[b].append((a, c))
    
    # Shortest distances from base 1
    dist_from_1 = dijkstra(graph, 1, N)
    
    # Shortest distance from base 1 to T
    dist_1_to_T = dist_from_1[T]
    
    # Since it's a round-trip, the shortest distance for 1→T→1 is 2 * dist(1, T)
    if dist_1_to_T == float('inf'):
        print(-1)
    else:
        print(2 * dist_1_to_T)

if __name__ == "__main__":
    main()

---

This editorial was generated by claude4.5opus.