結果
問題 |
No.848 なかよし旅行
|
ユーザー |
![]() |
提出日時 | 2025-04-15 23:54:27 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,513 bytes |
コンパイル時間 | 319 ms |
コンパイル使用メモリ | 82,104 KB |
実行使用メモリ | 103,296 KB |
最終ジャッジ日時 | 2025-04-15 23:55:23 |
合計ジャッジ時間 | 6,283 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 7 WA * 19 |
ソースコード
import heapq def dijkstra(n, graph, start): INF = float('inf') dist = [INF] * (n + 1) dist[start] = 0 heap = [] heapq.heappush(heap, (0, start)) while heap: current_dist, u = heapq.heappop(heap) if current_dist > dist[u]: continue for v, c in graph[u]: if dist[v] > dist[u] + c: dist[v] = dist[u] + c heapq.heappush(heap, (dist[v], v)) return dist n, m, P, Q, T = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a, b, c = map(int, input().split()) graph[a].append((b, c)) graph[b].append((a, c)) # Compute shortest paths from 1, P, Q d1 = dijkstra(n, graph, 1) dp = dijkstra(n, graph, P) dq = dijkstra(n, graph, Q) max_time = -1 # Check Scenario A: 1->P->Q->1 and 1->Q->P->1 time1 = d1[P] + dp[Q] + dq[1] if time1 <= T: max_time = max(max_time, T) time2 = d1[Q] + dq[P] + dp[1] if time2 <= T: max_time = max(max_time, T) # Check Scenario B: Split at some city X for X in range(1, n+1): max_pq = max(2 * dp[X], 2 * dq[X]) total_time = 2 * d1[X] + max_pq if total_time <= T: candidate = T - max_pq if candidate > max_time: max_time = candidate # Check Scenario D: Separate visits to P and Q time_p = 2 * d1[P] time_q = 2 * d1[Q] max_pq_separate = max(time_p, time_q) if max_pq_separate <= T: candidate = T - max_pq_separate max_time = max(max_time, candidate) print(max_time if max_time != -1 else -1)