結果

問題 No.2805 Go to School
コンテスト
ユーザー ntuda
提出日時 2024-07-13 17:05:02
言語 PyPy3
(7.3.15)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 980 bytes
コンパイル時間 404 ms
コンパイル使用メモリ 82,728 KB
実行使用メモリ 136,704 KB
最終ジャッジ日時 2025-04-09 15:41:45
合計ジャッジ時間 16,343 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 35 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import *

N, M, L, S, E0 = map(int, input().split())
ABT = [list(map(int, input().split())) for _ in range(M)]
T = [i - 1 for i in list(map(int, input().split()))]
E = [[] for _ in range(N)]

for a, b, t in ABT:
    a -= 1;
    b -= 1
    E[a].append((b, t))
    E[b].append((a, t))

INF = 10 ** 15
D = [[INF] * N for _ in range(2)]


def dijkstra(st, idx):
    D[idx][st] = 0
    q = [(0, st)]
    while q:
        d, u = heappop(q)
        # 下のifでTLE解消することがある
        if d > D[idx][u]: continue
        for i in E[u]:
            a, b = i
            if D[idx][a] > D[idx][u] + b:
                D[idx][a] = D[idx][u] + b
                heappush(q, (D[idx][a], a))
    return


dijkstra(0, 0)
dijkstra(N - 1, 1)
ans = INF
for t in T:
    if D[0][t] > S + E0:
        continue
    if D[0][t] < S:
        ans = min(ans, S + 1 + D[1][t])
    else:
        ans = min(ans, D[0][t] + D[1][t] + 1)
if ans == INF:
    print(-1)
else:
    print(ans)
0