結果

問題 No.848 なかよし旅行
コンテスト
ユーザー stng
提出日時 2022-07-23 20:39:12
言語 PyPy3
(7.3.17)
結果
TLE  
実行時間 -
コード長 1,004 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 443 ms
コンパイル使用メモリ 82,380 KB
実行使用メモリ 116,368 KB
最終ジャッジ日時 2024-07-05 11:09:38
合計ジャッジ時間 7,656 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from heapq import heappush, heappop
INF = 10 ** 9
def dijkstra(s, n): # (始点, ノード数)
    dist = [INF] * n
    hq = [(0, s)] # (distance, node)
    dist[s] = 0
    seen = [False] * n # ノードが確定済みかどうか
    while hq:
        v = heappop(hq)[1] # ノードを pop する
        seen[v] = True
        for to, cost in adj[v]: # ノード v に隣接しているノードに対して
            if seen[to] == False and dist[v] + cost < dist[to]:
                dist[to] = dist[v] + cost
                heappush(hq, (dist[to], to))
    return dist

n,m,p,q,t = map(int,input().split())
p -= 1
q -= 1
adj = [[] for i in range(n)]

for i in range(m):
    a,b,c = map(int,input().split())
    a -= 1
    b -= 1
    adj[a].append([b,c])
    adj[b].append([a,c])

fst = dijkstra(0,n)
ans = t-2*max(fst[p],fst[q])
for i in range(1,n):
    rt = dijkstra(i,n)
    tmp = 2*fst[i]
    tmp += 2*max(rt[p],rt[q])
    if tmp <= t:
        ans = max(ans,t-tmp+2*fst[i])

print(max(ans,-1))
0