結果
問題 | No.848 なかよし旅行 |
ユーザー | titia |
提出日時 | 2019-07-12 04:09:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 534 ms / 2,000 ms |
コード長 | 3,274 bytes |
コンパイル時間 | 311 ms |
コンパイル使用メモリ | 82,788 KB |
実行使用メモリ | 112,008 KB |
最終ジャッジ日時 | 2024-04-25 13:56:45 |
合計ジャッジ時間 | 7,087 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 534 ms
112,008 KB |
testcase_01 | AC | 39 ms
55,272 KB |
testcase_02 | AC | 35 ms
53,576 KB |
testcase_03 | AC | 37 ms
55,076 KB |
testcase_04 | AC | 37 ms
54,392 KB |
testcase_05 | AC | 38 ms
54,124 KB |
testcase_06 | AC | 52 ms
66,660 KB |
testcase_07 | AC | 37 ms
54,156 KB |
testcase_08 | AC | 85 ms
76,956 KB |
testcase_09 | AC | 104 ms
77,296 KB |
testcase_10 | AC | 86 ms
76,936 KB |
testcase_11 | AC | 269 ms
84,648 KB |
testcase_12 | AC | 289 ms
86,980 KB |
testcase_13 | AC | 309 ms
89,060 KB |
testcase_14 | AC | 248 ms
81,640 KB |
testcase_15 | AC | 311 ms
89,260 KB |
testcase_16 | AC | 394 ms
97,232 KB |
testcase_17 | AC | 317 ms
90,388 KB |
testcase_18 | AC | 264 ms
83,932 KB |
testcase_19 | AC | 270 ms
82,972 KB |
testcase_20 | AC | 199 ms
78,964 KB |
testcase_21 | AC | 351 ms
92,608 KB |
testcase_22 | AC | 259 ms
96,336 KB |
testcase_23 | AC | 204 ms
77,996 KB |
testcase_24 | AC | 36 ms
54,128 KB |
testcase_25 | AC | 403 ms
97,476 KB |
testcase_26 | AC | 35 ms
53,804 KB |
testcase_27 | AC | 36 ms
53,420 KB |
testcase_28 | AC | 36 ms
52,884 KB |
testcase_29 | AC | 36 ms
53,076 KB |
ソースコード
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): for j in range(1,N+1): if MINCOST_1[i] + MINCOST_1[j] + max(MINCOST_P[i]+MINCOST_P[j],MINCOST_Q[i]+MINCOST_Q[j]) <=T: ANS=max(ANS,T - max(MINCOST_P[i]+MINCOST_P[j],MINCOST_Q[i]+MINCOST_Q[j])) if ANS==-1: print(-1) else: print(ANS)