結果
問題 |
No.848 なかよし旅行
|
ユーザー |
|
提出日時 | 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 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
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)