結果
問題 | No.848 なかよし旅行 |
ユーザー | persimmon-persimmon |
提出日時 | 2021-06-21 16:22:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,318 ms / 2,000 ms |
コード長 | 1,808 bytes |
コンパイル時間 | 544 ms |
コンパイル使用メモリ | 86,572 KB |
実行使用メモリ | 142,028 KB |
最終ジャッジ日時 | 2023-09-05 01:53:37 |
合計ジャッジ時間 | 11,731 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge15 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,318 ms
142,028 KB |
testcase_01 | AC | 80 ms
71,108 KB |
testcase_02 | AC | 77 ms
71,048 KB |
testcase_03 | AC | 77 ms
71,204 KB |
testcase_04 | AC | 78 ms
71,236 KB |
testcase_05 | AC | 78 ms
71,044 KB |
testcase_06 | AC | 94 ms
76,200 KB |
testcase_07 | AC | 80 ms
71,188 KB |
testcase_08 | AC | 126 ms
77,564 KB |
testcase_09 | AC | 150 ms
79,008 KB |
testcase_10 | AC | 133 ms
78,304 KB |
testcase_11 | AC | 382 ms
90,224 KB |
testcase_12 | AC | 437 ms
93,648 KB |
testcase_13 | AC | 458 ms
97,708 KB |
testcase_14 | AC | 356 ms
85,596 KB |
testcase_15 | AC | 430 ms
98,072 KB |
testcase_16 | AC | 562 ms
111,624 KB |
testcase_17 | AC | 427 ms
99,268 KB |
testcase_18 | AC | 368 ms
88,972 KB |
testcase_19 | AC | 352 ms
87,092 KB |
testcase_20 | AC | 246 ms
79,900 KB |
testcase_21 | AC | 450 ms
104,308 KB |
testcase_22 | AC | 368 ms
108,572 KB |
testcase_23 | AC | 248 ms
79,016 KB |
testcase_24 | AC | 75 ms
70,948 KB |
testcase_25 | AC | 585 ms
110,020 KB |
testcase_26 | AC | 76 ms
71,124 KB |
testcase_27 | AC | 75 ms
71,056 KB |
testcase_28 | AC | 75 ms
71,156 KB |
testcase_29 | AC | 75 ms
70,912 KB |
ソースコード
from heapq import heappop,heappush def main0(n,m,p,q,t,abc): p,q=p-1,q-1 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') from0=[inf]*n fromp=[inf]*n fromq=[inf]*n from0[0]=0 todo=[[0,0]] while todo: d,v=heappop(todo) if from0[v]<d:continue for nv,nd in g[v]: if from0[nv]>d+nd: from0[nv]=d+nd heappush(todo,[d+nd,nv]) fromp[p]=0 todo=[[0,p]] while todo: d,v=heappop(todo) if fromp[v]<d:continue for nv,nd in g[v]: if fromp[nv]>d+nd: fromp[nv]=d+nd heappush(todo,[d+nd,nv]) fromq[q]=0 todo=[[0,q]] while todo: d,v=heappop(todo) if fromq[v]<d:continue for nv,nd in g[v]: if fromq[nv]>d+nd: fromq[nv]=d+nd heappush(todo,[d+nd,nv]) # 別行動しない0->p->q->0 # vで別行動をはじめる。 # 0->v->p->v->0 # 0->v->q->v->0 # vで別行動をはじめるとする。v->p,q最短距離で向かい、再びvで合流するのが最適か。合流の位置はvが最適とは限らない。 # v->pのパス:[2,2,2], v->q:[2,2]ならqに行った人はvに戻ってきた後pに一歩近づいた方が合流が早くなる。 tmp=from0[p]+fromp[q]+fromq[0] #print(from0) #print(fromp) #print(fromq) if tmp<=t:return t ans=-1 for v1 in range(n): for v2 in range(n): # v1で別行動してv2で合流する tmp=from0[v1] tmp+=max(fromp[v1]+fromp[v2],fromq[v1]+fromq[v2]) tmp+=from0[v2] if tmp<=t: ans=max(ans,t-max(fromp[v1]+fromp[v2],fromq[v1]+fromq[v2])) return ans if __name__=='__main__': n,m,p,q,t=map(int,input().split()) abc=[list(map(int,input().split())) for _ in range(m)] ret0=main0(n,m,p,q,t,abc) print(ret0)