結果

問題 No.807 umg tours
ユーザー roaris
提出日時 2019-08-04 19:37:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,347 ms / 4,000 ms
コード長 1,861 bytes
コンパイル時間 222 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 147,488 KB
最終ジャッジ日時 2024-11-23 19:35:30
合計ジャッジ時間 20,872 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappush, heappop
from collections import defaultdict
import sys
input = sys.stdin.readline

def dijkstra(start):
    distance0 = [10**18 for _ in range(N+1)]
    distance1 = [10**18 for _ in range(N+1)]
    distance0[start] = 0
    distance1[start] = 0
    priority_queue = []
    
    heappush(priority_queue, (distance0[start], start, 0))
    heappush(priority_queue, (distance1[start], start, 1))
    
    while len(priority_queue) > 0:
        current_dist, current_node, state = heappop(priority_queue)
        
        if (state == 0 and distance0[current_node] < current_dist) or (state == 1 and distance1[current_node] < current_dist):
            continue
       
        if state == 0:
            for next_node, w in adj_dict[current_node]:
                if distance0[next_node] > distance0[current_node] + w:
                    distance0[next_node] = distance0[current_node] + w
                    heappush(priority_queue, (distance0[next_node], next_node, 0))
                if distance1[next_node] > distance0[current_node]:
                    distance1[next_node] = distance0[current_node]
                    heappush(priority_queue, (distance1[next_node], next_node, 1))
        else:
            for next_node, w in adj_dict[current_node]:
                if distance1[next_node] > distance1[current_node] + w:
                    distance1[next_node] = distance1[current_node] + w
                    heappush(priority_queue, (distance1[next_node], next_node, 1))
    
    return distance0, distance1

N, M = map(int, input().split())
adj_dict = defaultdict(list)

for _ in range(M):
    a_i, b_i, c_i = map(int, input().split())
    adj_dict[a_i].append((b_i, c_i))
    adj_dict[b_i].append((a_i, c_i))

distance0, distance1 = dijkstra(1)

for i in range(1, N+1):
    ans = distance0[i] + distance1[i]
    print(ans)
0