結果

問題 No.807 umg tours
ユーザー gew1fw
提出日時 2025-06-12 17:03:31
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,677 ms / 4,000 ms
コード長 2,465 bytes
コンパイル時間 205 ms
コンパイル使用メモリ 82,396 KB
実行使用メモリ 193,924 KB
最終ジャッジ日時 2025-06-12 17:04:10
合計ジャッジ時間 25,770 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    M = int(data[idx+1])
    idx += 2

    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        a = int(data[idx])
        b = int(data[idx+1])
        c = int(data[idx+2])
        adj[a].append((b, c))
        adj[b].append((a, c))
        idx += 3

    # Compute d0 using Dijkstra
    INF = float('inf')
    d0 = [INF] * (N + 1)
    d0[1] = 0
    heap = []
    heapq.heappush(heap, (0, 1))
    while heap:
        dist, u = heapq.heappop(heap)
        if dist > d0[u]:
            continue
        for v, c in adj[u]:
            if d0[v] > d0[u] + c:
                d0[v] = d0[u] + c
                heapq.heappush(heap, (d0[v], v))

    # Compute min_d0_neighbor for each i
    min_d0_neighbor = [INF] * (N + 1)
    for u in range(1, N + 1):
        if not adj[u]:
            continue
        min_d = INF
        for v, c in adj[u]:
            if d0[v] < min_d:
                min_d = d0[v]
        min_d0_neighbor[u] = min_d

    # Compute d_forward using modified Dijkstra
    dist = [[INF] * 2 for _ in range(N + 1)]
    dist[1][0] = 0
    heap = []
    heapq.heappush(heap, (0, 1, 0))
    while heap:
        current_dist, u, used = heapq.heappop(heap)
        if current_dist > dist[u][used]:
            continue
        for v, c in adj[u]:
            if used == 0:
                # Option to use the ticket
                new_dist = current_dist + 0
                if new_dist < dist[v][1]:
                    dist[v][1] = new_dist
                    heapq.heappush(heap, (new_dist, v, 1))
                # Option to not use the ticket
                new_dist = current_dist + c
                if new_dist < dist[v][0]:
                    dist[v][0] = new_dist
                    heapq.heappush(heap, (new_dist, v, 0))
            else:
                new_dist = current_dist + c
                if new_dist < dist[v][1]:
                    dist[v][1] = new_dist
                    heapq.heappush(heap, (new_dist, v, 1))

    d_forward = [0] * (N + 1)
    for i in range(1, N + 1):
        d_forward[i] = dist[i][1]

    # Compute and print the answers
    for i in range(1, N + 1):
        option1 = 2 * d0[i]
        option2 = d_forward[i] + d0[i]
        option3 = d0[i] + min_d0_neighbor[i]
        ans = min(option1, option2, option3)
        print(ans)

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