結果
問題 |
No.614 壊れたキャンパス
|
ユーザー |
|
提出日時 | 2022-12-16 17:27:49 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,373 bytes |
コンパイル時間 | 338 ms |
コンパイル使用メモリ | 82,428 KB |
実行使用メモリ | 430,848 KB |
最終ジャッジ日時 | 2024-11-15 22:19:53 |
合計ジャッジ時間 | 24,500 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 TLE * 4 |
ソースコード
import heapq INF = 1 << 60 n, m, k, s, t = map(int, input().split()) s -= 1 t -= 1 idx = {} idx.setdefault((0, s), len(idx)) idx.setdefault((n - 1, t), len(idx)) adj = [[0, k - 1] for _ in range(n)] adj[0].append(s) adj[n - 1].append(t) arcs = [] for _ in range(m): a, b, c = map(int, input().split()) a -= 1 b -= 1 c -= 1 idx.setdefault((a, b), len(idx)) idx.setdefault((a + 1, c), len(idx)) arcs.append((idx[(a, b)], idx[(a + 1, c)], 0)) adj[a].append(b) adj[a + 1].append(c) edges = [] for b in range(n): floors = sorted(list(set(adj[b]))) for i in range(len(floors) - 1): idx.setdefault((b, floors[i]), len(idx)) idx.setdefault((b, floors[i + 1]), len(idx)) u = idx[(b, floors[i])] v = idx[(b, floors[i + 1])] cost = floors[i + 1] - floors[i] edges.append((u, v, cost)) g = [[] for _ in range(len(idx))] for u, v, c in arcs: g[u].append((v, c)) for u, v, c in edges: g[u].append((v, c)) g[v].append((u, c)) dist = [INF for _ in range(len(idx))] src = idx[(0, s)] dst = idx[(n - 1, t)] dist[src] = 0 hp = [(dist[src], src)] while len(hp) > 0: cd, cur = heapq.heappop(hp) if cd > dist[cur]: continue for nxt, cost in g[cur]: if dist[cur] + cost < dist[nxt]: dist[nxt] = dist[cur] + cost heapq.heappush(hp, (dist[nxt], nxt)) if dist[dst] < INF: print(dist[dst]) else: print("-1")