結果

問題 No.848 なかよし旅行
コンテスト
ユーザー persimmon-persimmon
提出日時 2022-03-31 16:09:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,143 ms / 2,000 ms
コード長 1,323 bytes
コンパイル時間 159 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 140,140 KB
最終ジャッジ日時 2024-11-17 03:01:59
合計ジャッジ時間 9,126 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappop,heappush
def main(n,m,p,q,t,abc):
    # 二人は街iまで一緒に行き、そこから別行動してp,qへ向かう。jで合流。
    # max(Tip+Tjp,Tiq+Tjq)の最小値を求めればいい
    # T>=T1i+T1j+max(Tip+Tjp,Tiq+Tjq)を満たすi,jの内、max(Tip+Tjp,Tiq+Tjq)が最小となるi,j
    # 1,p,qから各街への最短時間を記録し、i,jは全探索
    g=[[] for _ in range(n)]
    for a,b,c in abc:
        a,b=a-1,b-1
        g[a].append([b,c])
        g[b].append([a,c])
    inf=float('inf')
    p,q=p-1,q-1
    d1=[inf]*n
    dp=[inf]*n
    dq=[inf]*n
    for s,dd in zip([0,p,q],[d1,dp,dq]):
        que=[[0,s]]
        dd[s]=0
        while que:
            d,x=heappop(que)
            if dd[x]<d:continue
            for nx,c in g[x]:
                nd=d+c
                if dd[nx]>nd:
                    dd[nx]=nd
                    heappush(que,[nd,nx])
    if d1[p]+dp[q]+dq[0]<=t:return t
    ret=-1
    for i in range(n):
        for j in range(n):
            if d1[i]+max(dq[i]+dq[j],dp[i]+dp[j])+d1[j]<=t:
                ret=max(ret,t-max(dq[i]+dq[j],dp[i]+dp[j]))
    return ret

if __name__=='__main__':
    n,m,p,q,t=map(int,input().split())
    abc=[list(map(int,input().split())) for _ in range(m)]
    ret=main(n,m,p,q,t,abc)
    print(ret)
0