概要

拠点 \(1\) から出発し、拠点 \(T\) を少なくとも1回訪問した後、再び拠点 \(1\) に戻る最短時間を求める問題。

考察

この問題は、単純に「拠点 \(1\) → 拠点 \(T\) → 拠点 \(1\)」の経路を探すだけではなく、最短経路を求める必要があるため、ダイクストラ法などの最短経路アルゴリズムが必要になります。

素朴な方法として、すべての経路を全探索する方法が考えられますが、頂点数 \(N\) が最大 \(10^5\)、辺数 \(M\) も最大 \(2 \times 10^5\) となるため、現実的ではありません（TLE）。また、同じ頂点や辺を複数回通ることが許されているため、DFSなどで探索しても無限ループに陥る可能性があります。

重要な観察は、「拠点 \(1\) から拠点 \(T\) への最短距離」と「拠点 \(T\) から拠点 \(1\) への最短距離」をそれぞれ求めれば良いということです。これはグラフが無向なので、同じ最短距離になりますが、それぞれを別々に求めることで経由地などを気にせずシンプルに計算できます。

したがって、以下の2つの最短距離を求めれば十分です： - 拠点 \(1\) から拠点 \(T\) への最短距離 - 拠点 \(T\) から拠点 \(1\) への最短距離

もし、どちらか一方でも到達不能であれば、条件を満たす経路は存在しないため -1 を出力します。

アルゴリズム

1. 無向グラフを隣接リスト形式で構築する。
2. ダイクストラ法を用いて以下を計算：
   • dist_from_1[v]: 拠点 \(1\) からの最短距離（各頂点 \(v\) に対して）
   • dist_from_T[v]: 拠点 \(T\) からの最短距離（各頂点 \(v\) に対して）
3. dist_from_1[T] と dist_from_T[1] が共に有限値であれば、それらの和が答え。
4. どちらかが無限大（到達不能）なら -1 を出力。

計算量

• 時間計算量: \(O((N + M) \log N)\)
  • ダイクストラ法を2回実行。それぞれ \(O((N + M) \log N)\)
• 空間計算量: \(O(N + M)\)
  • 隣接リストと距離配列の使用量

実装のポイント

• 無向グラフなので、入力の辺 \((A_i, B_i)\) に対して両方向にエッジを追加すること。
• ダイクストラ法では、優先度付きキュー（heapq）を使うことで効率的に最小コストの頂点を取り出せる。
• 到達不能なケースを検出するために、距離が inf（無限大）かどうかをチェックする。

## ソースコード

```python
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()

この解説は qwen3-coder-480b によって生成されました。