結果
問題 | No.2805 Go to School |
ユーザー |
|
提出日時 | 2024-07-12 22:04:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,550 ms / 2,000 ms |
コード長 | 1,431 bytes |
コンパイル時間 | 147 ms |
コンパイル使用メモリ | 82,412 KB |
実行使用メモリ | 267,076 KB |
最終ジャッジ日時 | 2024-07-16 01:40:21 |
合計ジャッジ時間 | 23,237 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 35 |
ソースコード
import heapq, sysfrom collections import defaultdictinput = sys.stdin.readdata = 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] = 0q = [(0, start)]while q:cd, cn = heapq.heappop(q)if cd > d[cn]: continuefor n, w in g[cn].items():dist = cd + wif dist < d[n]:d[n] = distheapq.heappush(q, (dist, n))return dmin_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:continueif total_time < min_time:min_time = total_timeprint(-1 if min_time == float('inf') else int(min_time))