結果

問題 No.807 umg tours
ユーザー roarisroaris
提出日時 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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 58 ms
61,056 KB
testcase_01 AC 59 ms
62,464 KB
testcase_02 AC 61 ms
64,768 KB
testcase_03 AC 62 ms
63,232 KB
testcase_04 AC 55 ms
61,312 KB
testcase_05 AC 52 ms
61,312 KB
testcase_06 AC 58 ms
63,488 KB
testcase_07 AC 64 ms
65,024 KB
testcase_08 AC 43 ms
54,400 KB
testcase_09 AC 47 ms
54,784 KB
testcase_10 AC 47 ms
54,400 KB
testcase_11 AC 912 ms
110,148 KB
testcase_12 AC 1,264 ms
115,964 KB
testcase_13 AC 1,527 ms
125,088 KB
testcase_14 AC 687 ms
98,264 KB
testcase_15 AC 504 ms
93,080 KB
testcase_16 AC 1,410 ms
126,280 KB
testcase_17 AC 2,071 ms
140,440 KB
testcase_18 AC 1,915 ms
138,940 KB
testcase_19 AC 1,816 ms
135,208 KB
testcase_20 AC 918 ms
111,592 KB
testcase_21 AC 944 ms
112,688 KB
testcase_22 AC 459 ms
90,548 KB
testcase_23 AC 405 ms
87,636 KB
testcase_24 AC 1,120 ms
140,412 KB
testcase_25 AC 2,347 ms
147,488 KB
権限があれば一括ダウンロードができます

ソースコード

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