結果

問題 No.848 なかよし旅行
コンテスト
ユーザー simamumu
提出日時 2019-07-05 21:56:38
言語 Python3
(3.14.3 + numpy 2.4.2 + scipy 1.17.0)
結果
TLE  
実行時間 -
コード長 1,314 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 277 ms
コンパイル使用メモリ 12,672 KB
実行使用メモリ 66,304 KB
最終ジャッジ日時 2024-10-06 21:34:59
合計ジャッジ時間 6,861 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(input())
def inpl(): return list(map(int, input().split()))
def inpl_str(): return list(input().split())

def Dijkustra(lines,N,s):
    weight = [INF]*N
    weight[s] = 0

    def search (s,w_0,q,weight): #s->t
    	for line in list(lines[s]):
    		t = line[0]
    		w = w_0 + line[1]
    		if weight[t] > w:
    			heapq.heappush(q, [w,t])
    			weight[t] = w

    q = [[0,s]]
    heapq.heapify(q)
    while q:
    	w,n = heapq.heappop(q)
    	search(n,w,q,weight)

    return weight

N,M,P,Q,T = inpl()
S,P,Q = 0,P-1,Q-1
lines = defaultdict(set)
for _ in range(M):
    a,b,c = inpl()
    a,b = a-1,b-1
    lines[a].add((b,c))
    lines[b].add((a,c))

weight_S = Dijkustra(lines,N,S)
weight_P = Dijkustra(lines,N,P)
weight_Q = Dijkustra(lines,N,Q)

SP = weight_S[P]
SQ = weight_S[Q]
PQ = weight_P[Q]

if SP + PQ + SQ <= T:
    print(T)
elif SP*2 > T or SQ*2 > T:
    print(-1)
else:
    ans = 0
    for X in range(N):
        SX = weight_S[X]
        PX,QX = weight_P[X], weight_Q[X]
        #print(X,SX,PX,QX)
        d = max(PX,QX)
        if d*2 + SX*2 <= T:
            ans = max(ans,T-d*2)
    print(ans)
0