結果

問題 No.807 umg tours
ユーザー roarisroaris
提出日時 2019-08-04 19:37:27
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,703 ms / 4,000 ms
コード長 1,861 bytes
コンパイル時間 520 ms
コンパイル使用メモリ 82,304 KB
実行使用メモリ 147,624 KB
最終ジャッジ日時 2024-05-02 23:57:09
合計ジャッジ時間 24,330 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 53 ms
61,544 KB
testcase_01 AC 56 ms
63,232 KB
testcase_02 AC 66 ms
64,768 KB
testcase_03 AC 64 ms
63,488 KB
testcase_04 AC 58 ms
61,696 KB
testcase_05 AC 56 ms
61,696 KB
testcase_06 AC 62 ms
63,872 KB
testcase_07 AC 66 ms
65,536 KB
testcase_08 AC 49 ms
54,144 KB
testcase_09 AC 49 ms
54,272 KB
testcase_10 AC 49 ms
54,656 KB
testcase_11 AC 1,138 ms
110,156 KB
testcase_12 AC 1,459 ms
116,336 KB
testcase_13 AC 1,797 ms
125,092 KB
testcase_14 AC 828 ms
98,388 KB
testcase_15 AC 601 ms
93,196 KB
testcase_16 AC 1,729 ms
126,148 KB
testcase_17 AC 2,420 ms
140,564 KB
testcase_18 AC 2,238 ms
139,196 KB
testcase_19 AC 2,159 ms
135,464 KB
testcase_20 AC 1,053 ms
111,464 KB
testcase_21 AC 1,090 ms
112,568 KB
testcase_22 AC 512 ms
90,932 KB
testcase_23 AC 434 ms
87,640 KB
testcase_24 AC 1,161 ms
140,676 KB
testcase_25 AC 2,703 ms
147,624 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