結果

問題 No.848 なかよし旅行
ユーザー ああいい
提出日時 2022-04-20 11:31:41
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 487 ms / 2,000 ms
コード長 1,026 bytes
コンパイル時間 268 ms
コンパイル使用メモリ 82,456 KB
実行使用メモリ 102,648 KB
最終ジャッジ日時 2024-06-11 12:19:48
合計ジャッジ時間 7,182 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

N,M,P,Q,T = map(int,input().split())
P -= 1
Q -= 1
G = [[] for _ in range(N)]
for _ in range(M):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    G[a].append((b,c))
    G[b].append((a,c))
inf = 10 ** 9 * 2000 + 1000
dist = [[inf] * N for _ in range(3)]
from heapq import heappop,heappush
for i in range(3):
    if i == 0:
        s = 0
    elif i == 1:
        s = P
    else:
        s = Q
    q = [(0,s)]
    dist[i][s] = 0
    while q:
        d,now = heappop(q)
        if dist[i][now] < d:continue
        for v,c in G[now]:
            if dist[i][v] > d + c:
                dist[i][v] = d + c
                heappush(q,(d + c,v))

import sys
t = dist[0][P] + dist[1][Q] + dist[0][Q]
if t <= T:
    print(T)
    exit()
ans = -1


for u in range(N):
    for v in range(u,N):
        t = max(dist[1][u] + dist[1][v],dist[2][u] + dist[2][v])
        tmp = dist[0][u] + t + dist[0][v]
        if tmp > T:continue
        #t = dist[0][u] + dist[0][v]
        if T - t > ans:
            ans = T - t
print(ans)
0