結果
問題 |
No.848 なかよし旅行
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:52:12 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,986 bytes |
コンパイル時間 | 197 ms |
コンパイル使用メモリ | 82,520 KB |
実行使用メモリ | 116,264 KB |
最終ジャッジ日時 | 2025-03-31 17:52:52 |
合計ジャッジ時間 | 5,895 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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: cost, u = heapq.heappop(heap) if cost > dist[u]: continue for v, c in adj[u]: if dist[v] > dist[u] + c: dist[v] = dist[u] + c heapq.heappush(heap, (dist[v], v)) return dist def main(): import sys input = sys.stdin.read().split() idx = 0 N, M, P, Q, T = map(int, input[idx:idx+5]) idx +=5 adj = [[] for _ in range(N+1)] for _ in range(M): a, b, c = map(int, input[idx:idx+3]) idx +=3 adj[a].append((b, c)) adj[b].append((a, c)) # Dijkstra from 1, P, Q d1 = dijkstra(N, adj, 1) dp = dijkstra(N, adj, P) dq = dijkstra(N, adj, Q) max_time = -1 # Case A: 1 -> P -> Q ->1 time_caseA = d1[P] + dp[Q] + d1[Q] if time_caseA <= T: max_time = max(max_time, T) # Case B: 1 -> Q -> P ->1 (unnecessary as it's same as A for undirected graph) # Case C: for all possible X best_caseC = -1 for X in range(1, N+1): if d1[X] == float('inf'): continue dX_p = dp[X] # P to X is same as X to P in undirected graph dX_q = dq[X] # Q to X is same as X to Q time_separate = max(2 * dX_p, 2 * dX_q) total_time = 2 * d1[X] + time_separate if total_time > T: continue candidate = T - time_separate if candidate > best_caseC: best_caseC = candidate if best_caseC != -1: max_time = max(max_time, best_caseC) # Case D: separate travel time_p = 2 * d1[P] time_q = 2 * d1[Q] max_separate = max(time_p, time_q) if max_separate <= T: candidate = T - max_separate max_time = max(max_time, candidate) print(max_time if max_time != -1 else -1) if __name__ == '__main__': main()