結果

問題 No.848 なかよし旅行
ユーザー titiatitia
提出日時 2019-07-12 04:00:07
言語 Python3
(3.11.6 + numpy 1.26.0 + scipy 1.11.3)
結果
WA  
実行時間 -
コード長 3,157 bytes
コンパイル時間 423 ms
コンパイル使用メモリ 10,892 KB
実行使用メモリ 55,560 KB
最終ジャッジ日時 2023-07-29 01:42:59
合計ジャッジ時間 10,606 ms
ジャッジサーバーID
(参考情報)
judge15 / judge11
このコードへのチャレンジ(β)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,354 ms
55,560 KB
testcase_01 AC 17 ms
8,316 KB
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 17 ms
8,424 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 17 ms
8,304 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 AC 439 ms
30,308 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 AC 40 ms
9,736 KB
testcase_21 WA -
testcase_22 WA -
testcase_23 WA -
testcase_24 AC 18 ms
8,300 KB
testcase_25 WA -
testcase_26 AC 17 ms
8,124 KB
testcase_27 AC 17 ms
8,292 KB
testcase_28 AC 17 ms
8,396 KB
testcase_29 AC 17 ms
8,324 KB
権限があれば一括ダウンロードができます

ソースコード

diff #

N,M,P,Q,T=map(int,input().split())

EDGE=[list(map(int,input().split())) for i in range(M)]

#グラフの重みつき最短距離(ダイクストラ法)

import heapq
#heapqは最初の要素が最小値になるデータ構造.
#第一要素に関して処理を行うので,最初の要素を最大値にしたい場合は(-x,x)に対してheapqすれば良い.


COST_vertex=[[] for i in range(N+1)]#iから他の点への辺とcostを列挙
for a,b,c in EDGE:
    COST_vertex[a].append((b,c))
    COST_vertex[b].append((a,c))#双方向の場合

MINCOST_1=[float("inf")]*(N+1)#求めたいリスト:startから頂点iへの最短距離
start=1

checking=[(0,start)]#start時点のcostは0.最初はこれをチェックする.
MINCOST_1[start]=0
while checking:
    cost,checktown=heapq.heappop(checking)
    #cost,checktownからの行き先をcheck.
    #cost最小なものを確定し,確定したものはcheckingから抜く.
    if MINCOST_1[checktown]<cost:#確定したものを再度チェックしなくて良い.
        continue    
    for to,co in COST_vertex[checktown]:
        if MINCOST_1[to]>cost+co:
            MINCOST_1[to]=cost+co
            #MINCOST候補に追加
            heapq.heappush(checking,(cost+co,to))
            #次にチェックする候補たちをcheckingに入れる.

MINCOST_P=[float("inf")]*(N+1)#求めたいリスト:startから頂点iへの最短距離
start=P

checking=[(0,start)]#start時点のcostは0.最初はこれをチェックする.
MINCOST_P[start]=0
while checking:
    cost,checktown=heapq.heappop(checking)
    #cost,checktownからの行き先をcheck.
    #cost最小なものを確定し,確定したものはcheckingから抜く.
    if MINCOST_P[checktown]<cost:#確定したものを再度チェックしなくて良い.
        continue    
    for to,co in COST_vertex[checktown]:
        if MINCOST_P[to]>cost+co:
            MINCOST_P[to]=cost+co
            #MINCOST候補に追加
            heapq.heappush(checking,(cost+co,to))
            #次にチェックする候補たちをcheckingに入れる.

MINCOST_Q=[float("inf")]*(N+1)#求めたいリスト:startから頂点iへの最短距離
start=Q

checking=[(0,start)]#start時点のcostは0.最初はこれをチェックする.
MINCOST_Q[start]=0
while checking:
    cost,checktown=heapq.heappop(checking)
    #cost,checktownからの行き先をcheck.
    #cost最小なものを確定し,確定したものはcheckingから抜く.
    if MINCOST_Q[checktown]<cost:#確定したものを再度チェックしなくて良い.
        continue    
    for to,co in COST_vertex[checktown]:
        if MINCOST_Q[to]>cost+co:
            MINCOST_Q[to]=cost+co
            #MINCOST候補に追加
            heapq.heappush(checking,(cost+co,to))
            #次にチェックする候補たちをcheckingに入れる.

if MINCOST_1[P]+MINCOST_P[Q]+MINCOST_Q[1]<=T:
    print(T)

else:
    ANS=-1
    for i in range(1,N+1):
        if MINCOST_1[i]*2+max(MINCOST_P[i],MINCOST_Q[i])*2 <=T:
            ANS=max(ANS,T-max(MINCOST_P[i],MINCOST_Q[i])*2)

    if ANS==-1:
        print(-1)
    else:
        print(ANS)
0