結果

問題 No.848 なかよし旅行
ユーザー persimmon-persimmonpersimmon-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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,143 ms
140,140 KB
testcase_01 AC 43 ms
53,376 KB
testcase_02 AC 40 ms
52,352 KB
testcase_03 AC 41 ms
53,376 KB
testcase_04 AC 40 ms
53,376 KB
testcase_05 AC 40 ms
53,248 KB
testcase_06 AC 61 ms
64,896 KB
testcase_07 AC 42 ms
53,632 KB
testcase_08 AC 95 ms
76,544 KB
testcase_09 AC 124 ms
78,172 KB
testcase_10 AC 100 ms
76,660 KB
testcase_11 AC 265 ms
86,420 KB
testcase_12 AC 300 ms
90,100 KB
testcase_13 AC 328 ms
94,500 KB
testcase_14 AC 223 ms
81,360 KB
testcase_15 AC 317 ms
94,016 KB
testcase_16 AC 425 ms
108,128 KB
testcase_17 AC 305 ms
97,176 KB
testcase_18 AC 247 ms
85,748 KB
testcase_19 AC 237 ms
84,376 KB
testcase_20 AC 199 ms
78,520 KB
testcase_21 AC 342 ms
101,948 KB
testcase_22 AC 280 ms
106,112 KB
testcase_23 AC 196 ms
77,952 KB
testcase_24 AC 40 ms
52,864 KB
testcase_25 AC 424 ms
107,992 KB
testcase_26 AC 39 ms
52,992 KB
testcase_27 AC 39 ms
52,864 KB
testcase_28 AC 40 ms
52,864 KB
testcase_29 AC 40 ms
52,608 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