結果

問題 No.1320 Two Type Min Cost Cycle
コンテスト
ユーザー lam6er
提出日時 2025-03-20 21:12:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,015 ms / 2,000 ms
コード長 2,200 bytes
コンパイル時間 147 ms
コンパイル使用メモリ 82,412 KB
実行使用メモリ 151,472 KB
最終ジャッジ日時 2025-03-20 21:13:44
合計ジャッジ時間 15,317 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 57
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def dijkstra(adj, start, end):
    n = len(adj) - 1  # nodes are 1-based
    INF = 1 << 60
    dist = [INF] * (n + 1)
    dist[start] = 0
    heap = [(0, start)]
    while heap:
        d, u = heapq.heappop(heap)
        if u == end:
            return d
        if d > dist[u]:
            continue
        for v, w in adj[u]:
            if dist[v] > d + w:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return INF

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    T = int(input[ptr])
    ptr += 1
    N = int(input[ptr])
    ptr +=1
    M = int(input[ptr])
    ptr +=1
    original_edges = []
    adj = [[] for _ in range(N+1)]  # 1-based
    for _ in range(M):
        u = int(input[ptr])
        ptr +=1
        v = int(input[ptr])
        ptr +=1
        w = int(input[ptr])
        ptr +=1
        original_edges.append( (u, v, w) )
        if T == 0:
            adj[u].append( (v, w) )
            adj[v].append( (u, w) )
        else:
            adj[u].append( (v, w) )
    min_cycle = 1 << 60
    for edge in original_edges:
        u_curr, v_curr, w_curr = edge
        if T == 0:
            # Create temp_adj by removing u_curr <-> v_curr edges
            temp_adj = [[] for _ in range(N+1)]
            for u in range(1, N+1):
                for (v, w) in adj[u]:
                    if (u == u_curr and v == v_curr) or (u == v_curr and v == u_curr):
                        continue
                    temp_adj[u].append( (v, w) )
            # Run Dijkstra from u_curr to v_curr
            dist = dijkstra(temp_adj, u_curr, v_curr)
            if dist < (1 << 60):
                candidate = dist + w_curr
                if candidate < min_cycle:
                    min_cycle = candidate
        else:
            # T ==1 : Run Dijkstra from v_curr to u_curr
            dist = dijkstra(adj, v_curr, u_curr)
            if dist < (1 << 60):
                candidate = dist + w_curr
                if candidate < min_cycle:
                    min_cycle = candidate
    if min_cycle == (1 << 60):
        print(-1)
    else:
        print(min_cycle)

if __name__ == "__main__":
    main()
0