結果

問題 No.848 なかよし旅行
ユーザー persimmon-persimmonpersimmon-persimmon
提出日時 2022-03-31 16:09:53
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,198 ms / 2,000 ms
コード長 1,323 bytes
コンパイル時間 260 ms
コンパイル使用メモリ 86,432 KB
実行使用メモリ 140,536 KB
最終ジャッジ日時 2023-08-10 18:18:40
合計ジャッジ時間 10,254 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,198 ms
140,536 KB
testcase_01 AC 76 ms
71,116 KB
testcase_02 AC 74 ms
71,112 KB
testcase_03 AC 76 ms
71,112 KB
testcase_04 AC 74 ms
71,076 KB
testcase_05 AC 75 ms
70,724 KB
testcase_06 AC 92 ms
76,144 KB
testcase_07 AC 77 ms
71,080 KB
testcase_08 AC 122 ms
77,872 KB
testcase_09 AC 155 ms
79,044 KB
testcase_10 AC 126 ms
78,204 KB
testcase_11 AC 285 ms
87,964 KB
testcase_12 AC 323 ms
91,244 KB
testcase_13 AC 362 ms
96,076 KB
testcase_14 AC 258 ms
82,468 KB
testcase_15 AC 353 ms
95,912 KB
testcase_16 AC 460 ms
109,656 KB
testcase_17 AC 341 ms
98,424 KB
testcase_18 AC 296 ms
87,704 KB
testcase_19 AC 271 ms
85,384 KB
testcase_20 AC 207 ms
78,920 KB
testcase_21 AC 376 ms
102,800 KB
testcase_22 AC 307 ms
106,804 KB
testcase_23 AC 223 ms
78,388 KB
testcase_24 AC 72 ms
70,948 KB
testcase_25 AC 460 ms
109,772 KB
testcase_26 AC 75 ms
71,124 KB
testcase_27 AC 70 ms
71,004 KB
testcase_28 AC 71 ms
70,844 KB
testcase_29 AC 72 ms
71,112 KB
権限があれば一括ダウンロードができます

ソースコード

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