結果

問題 No.2805 Go to School
ユーザー NPNP
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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))
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0