結果

問題 No.1320 Two Type Min Cost Cycle
コンテスト
ユーザー LyricalMaestro
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff # 

## 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()
0