結果
問題 |
No.2805 Go to School
|
ユーザー |
|
提出日時 | 2024-07-12 22:04:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,598 ms / 2,000 ms |
コード長 | 1,431 bytes |
コンパイル時間 | 164 ms |
コンパイル使用メモリ | 82,324 KB |
実行使用メモリ | 267,120 KB |
最終ジャッジ日時 | 2025-04-09 15:39:43 |
合計ジャッジ時間 | 24,560 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 36 |
ソースコード
import heapq, sys from collections import defaultdict input = sys.stdin.read data = input().split() N, M, L, S, E = map(int, data[:5]) paths = [(int(data[i]), int(data[i+1]), int(data[i+2])) for i in range(5, 5 + 3 * M, 3)] toilets = list(map(int, data[5 + 3 * M:])) g = defaultdict(dict) for a, b, t in paths: g[a][b] = min(g[a].get(b, float('inf')), t) g[b][a] = min(g[b].get(a, float('inf')), t) def dijkstra(g, start): d = {i: float('inf') for i in g} d[start] = 0 q = [(0, start)] while q: cd, cn = heapq.heappop(q) if cd > d[cn]: continue for n, w in g[cn].items(): dist = cd + w if dist < d[n]: d[n] = dist heapq.heappush(q, (dist, n)) return d min_time_to = dijkstra(g, 1) reverse_g = defaultdict(dict) for a in g: for b in g[a]: reverse_g[b][a] = g[a][b] min_time_from = dijkstra(reverse_g, N) min_time = float('inf') for toilet in toilets: if toilet in min_time_to and toilet in min_time_from: arrival_time = min_time_to[toilet] if arrival_time < S: total_time = S + 1 + min_time_from[toilet] elif arrival_time <= S + E - 0.99: total_time = arrival_time + 1 + min_time_from[toilet] else: continue if total_time < min_time: min_time = total_time print(-1 if min_time == float('inf') else int(min_time))