結果
問題 |
No.848 なかよし旅行
|
ユーザー |
👑 ![]() |
提出日時 | 2025-08-06 00:28:29 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 368 ms / 2,000 ms |
コード長 | 1,506 bytes |
コンパイル時間 | 267 ms |
コンパイル使用メモリ | 82,356 KB |
実行使用メモリ | 101,792 KB |
最終ジャッジ日時 | 2025-08-06 00:28:37 |
合計ジャッジ時間 | 7,950 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 26 |
ソースコード
""" https://yukicoder.me/problems/no/848 N=2000 なので、分かれる町と合流地点を全探索? """ import sys from sys import stdin import math #重み有グラフの最短経路問題 #隣接リストは[隣接点,コスト]で入っていること #負の重不可 import heapq def Dijkstra(lis,start): ret = [float("inf")] * len(lis) ret[start] = 0 end_flag = [False] * len(lis) end_num = 0 q = [(0,start)] while len(q) > 0: ncost,now = heapq.heappop(q) if end_flag[now]: continue end_flag[now] = True end_num += 1 if end_num == len(lis): break for nex,ecost in lis[now]: if ret[nex] > ncost + ecost: ret[nex] = ncost + ecost heapq.heappush(q , (ret[nex] , nex)) return ret N,M,P,Q,T = map(int,stdin.readline().split()) P -= 1 Q -= 1 lis = [ [] for i in range(N) ] for i in range(M): u,v,c = map(int,stdin.readline().split()) u -= 1 v -= 1 lis[u].append( (v,c) ) lis[v].append( (u,c) ) Adis = Dijkstra(lis,0) Pdis = Dijkstra(lis,P) Qdis = Dijkstra(lis,Q) if max(Adis[P]*2,Adis[Q]*2) > T: print (-1) sys.exit() if Adis[P] + Pdis[Q] + Qdis[0] <= T: print (T) sys.exit() ans = 0 for v in range(N): for u in range(N): loss = max(Pdis[v] + Pdis[u], Qdis[v] + Qdis[u]) time = Adis[v] + Adis[u] + loss if time <= T: ans = max(ans, T-loss) print (ans)