結果
問題 |
No.2805 Go to School
|
ユーザー |
|
提出日時 | 2025-02-12 13:01:49 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,892 bytes |
コンパイル時間 | 410 ms |
コンパイル使用メモリ | 82,556 KB |
実行使用メモリ | 150,840 KB |
最終ジャッジ日時 | 2025-04-09 15:44:13 |
合計ジャッジ時間 | 18,784 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 WA * 1 |
ソースコード
import heapq from collections import defaultdict n,m,l,s,e=map(int,input().split()) def dijkstra(graph, start): """ ダイクストラ法を用いて、startから各頂点への最短距離を求めます。 Parameters: graph: dict 各頂点をキーとし、その頂点から出る辺を (隣接頂点, 重み) のタプルのリストとして持つ辞書 例: graph = { 0: [(1, 2), (2, 5)], 1: [(2, 1), (3, 3)], 2: [(3, 1)], 3: [] } start: 始点となる頂点 Returns: dist: dict 各頂点への最短距離を表す辞書。到達不能の場合は float('inf') が設定されます。 """ # 各頂点への最短距離を無限大で初期化(始点のみ0) dist = {vertex: float('inf') for vertex in graph} dist[start] = 0 # 優先度付きキュー(ヒープ)に (距離, 頂点) のペアを格納 queue = [(0, start)] while queue: current_dist, u = heapq.heappop(queue) # すでにより良い経路が見つかっている場合はスキップ if current_dist > dist[u]: continue # uから出る全ての辺について、最短距離を更新 for v, weight in graph[u]: new_dist = current_dist + weight if new_dist < dist[v]: dist[v] = new_dist heapq.heappush(queue, (new_dist, v)) return dist G=defaultdict(list) for _ in range(m): a,b,t=map(int,input().split()) G[a].append((b,t)) G[b].append((a,t)) D1=dijkstra(G,1) D2=dijkstra(G,n) T=list(map(int,input().split())) ans=float("inf") for i in T: if i in D1 and i in D2 and D1[i]<=s+e: ans=min(ans,max(s,D1[i])+1+D2[i]) print(ans if ans!=float("inf") else -1)