結果

問題 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 487 ms
102,648 KB
testcase_01 AC 38 ms
54,608 KB
testcase_02 AC 34 ms
53,204 KB
testcase_03 AC 36 ms
53,160 KB
testcase_04 AC 36 ms
54,616 KB
testcase_05 AC 38 ms
54,088 KB
testcase_06 AC 49 ms
63,488 KB
testcase_07 AC 38 ms
53,812 KB
testcase_08 AC 87 ms
76,424 KB
testcase_09 AC 109 ms
77,652 KB
testcase_10 AC 89 ms
76,564 KB
testcase_11 AC 196 ms
79,848 KB
testcase_12 AC 223 ms
81,768 KB
testcase_13 AC 232 ms
82,348 KB
testcase_14 AC 190 ms
79,200 KB
testcase_15 AC 224 ms
82,572 KB
testcase_16 AC 296 ms
87,164 KB
testcase_17 AC 257 ms
83,320 KB
testcase_18 AC 206 ms
80,096 KB
testcase_19 AC 191 ms
79,664 KB
testcase_20 AC 155 ms
77,728 KB
testcase_21 AC 237 ms
84,732 KB
testcase_22 AC 204 ms
87,452 KB
testcase_23 AC 141 ms
77,596 KB
testcase_24 AC 36 ms
53,428 KB
testcase_25 AC 294 ms
88,032 KB
testcase_26 AC 34 ms
54,048 KB
testcase_27 AC 32 ms
53,440 KB
testcase_28 AC 34 ms
54,320 KB
testcase_29 AC 34 ms
54,396 KB
権限があれば一括ダウンロードができます

ソースコード

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