結果
問題 |
No.1320 Two Type Min Cost Cycle
|
ユーザー |
|
提出日時 | 2025-05-04 15:37:04 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,382 ms / 2,000 ms |
コード長 | 2,451 bytes |
コンパイル時間 | 433 ms |
コンパイル使用メモリ | 82,484 KB |
実行使用メモリ | 87,052 KB |
最終ジャッジ日時 | 2025-05-04 15:37:21 |
合計ジャッジ時間 | 16,665 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 57 |
ソースコード
## https://yukicoder.me/problems/no/1864 import heapq MAX_INT = 10 ** 18 def found_min_cycle(N, base_i, next_nodes): fix = [MAX_INT] * N seen = [MAX_INT] * N parents = [-2] * N seen[base_i] = 0 parents[base_i] = -1 queue = [] heapq.heappush(queue, (0, base_i)) min_cycle = float("inf") while len(queue) > 0: cost, v = heapq.heappop(queue) if fix[v] < MAX_INT: continue fix[v] = cost for u, w in next_nodes[v]: if u == parents[v]: continue if fix[u] < MAX_INT: ans = fix[u] + fix[v] + w min_cycle = min(min_cycle, ans) continue new_w = w + cost if seen[u] > new_w: seen[u] = new_w parents[u] = v heapq.heappush(queue, (new_w, u)) return min_cycle def found_min_cycle2(N, base_i, next_nodes): fix = [MAX_INT] * N seen = [MAX_INT] * N parents = [-2] * N seen[base_i] = 0 parents[base_i] = -1 queue = [] heapq.heappush(queue, (0, base_i)) min_cycle = float("inf") while len(queue) > 0: cost, v = heapq.heappop(queue) if fix[v] < MAX_INT: continue fix[v] = cost for u, w in next_nodes[v]: if u == parents[v]: continue if u == base_i: ans = fix[v] + w min_cycle = min(min_cycle, ans) if fix[u] < MAX_INT: continue new_w = w + cost if seen[u] > new_w: seen[u] = new_w parents[u] = v heapq.heappush(queue, (new_w, u)) return min_cycle def main(): T = int(input()) N, M = map(int, input().split()) next_nodes = [[] for _ in range(N)] for _ in range(M): u,v, w = map(int, input().split()) next_nodes[ u -1 ].append((v - 1, w)) if T == 0: next_nodes[v - 1].append((u - 1, w)) answer_cycle = float("inf") for base_i in range(N): if T == 0: min_cycle = found_min_cycle(N, base_i, next_nodes) else: min_cycle = found_min_cycle2(N, base_i, next_nodes) answer_cycle = min(answer_cycle, min_cycle) if answer_cycle == float("inf"): print(-1) else: print(answer_cycle) if __name__ == '__main__': main()