結果
問題 |
No.848 なかよし旅行
|
ユーザー |
![]() |
提出日時 | 2025-04-16 00:01:30 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,764 bytes |
コンパイル時間 | 446 ms |
コンパイル使用メモリ | 81,388 KB |
実行使用メモリ | 115,524 KB |
最終ジャッジ日時 | 2025-04-16 00:03:35 |
合計ジャッジ時間 | 5,275 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 WA * 19 |
ソースコード
import heapq def dijkstra(n, adj, start): INF = float('inf') dist = [INF] * (n + 1) dist[start] = 0 heap = [(0, start)] while heap: d, u = heapq.heappop(heap) if d > dist[u]: continue for v, c in adj[u]: if dist[v] > d + c: dist[v] = d + c heapq.heappush(heap, (dist[v], v)) return dist def main(): import sys input = sys.stdin.read().split() idx = 0 N = int(input[idx]); idx +=1 M = int(input[idx]); idx +=1 P = int(input[idx]); idx +=1 Q = int(input[idx]); idx +=1 T = int(input[idx]); idx +=1 adj = [[] for _ in range(N+1)] for _ in range(M): a = int(input[idx]); idx +=1 b = int(input[idx]); idx +=1 c = int(input[idx]); idx +=1 adj[a].append((b, c)) adj[b].append((a, c)) d1 = dijkstra(N, adj, 1) dp = dijkstra(N, adj, P) dq = dijkstra(N, adj, Q) scenario1_time = d1[P] + d1[Q] + dp[Q] if scenario1_time <= T: print(T) return max_candidate = -1 # Scenario 3 time3_p = 2 * d1[P] time3_q = 2 * d1[Q] max_time3 = max(time3_p, time3_q) if max_time3 <= T: candidate3 = T - max_time3 max_candidate = max(max_candidate, candidate3) # Scenario 2 for X in range(1, N+1): a = dp[X] b = dq[X] max_ab = max(a, b) sum_scenario2 = 2 * (d1[X] + max_ab) if sum_scenario2 > T: continue candidate = T - 2 * max_ab if candidate > max_candidate: max_candidate = candidate if max_candidate >= 0: print(max_candidate) else: print(-1) if __name__ == "__main__": main()