結果

問題 No.848 なかよし旅行
コンテスト
ユーザー simamumu
提出日時 2019-07-05 22:02:32
言語 PyPy3
(7.3.15)
結果
TLE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,428 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 122,624 KB
最終ジャッジ日時 2024-11-07 09:54:57
合計ジャッジ時間 7,397 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 4
other TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff # 

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 X1 in range(N):
        SX1 = weight_S[X1]
        PX1,QX1 = weight_P[X1], weight_Q[X1]
        for X2 in range(X1,N):
            SX2 = weight_S[X2]
            PX2,QX2 = weight_P[X2], weight_Q[X2]
            d = max(PX1+PX2,QX1+QX2)
            if d + SX1 + SX2 <= T:
                ans = max(ans,T-d)
    print(ans)
0