結果
問題 | No.2805 Go to School |
ユーザー |
|
提出日時 | 2024-07-12 22:03:58 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,431 bytes |
コンパイル時間 | 340 ms |
コンパイル使用メモリ | 12,800 KB |
実行使用メモリ | 121,868 KB |
最終ジャッジ日時 | 2024-07-12 22:04:11 |
合計ジャッジ時間 | 11,217 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 6 TLE * 1 -- * 27 |
ソースコード
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))