Submission #50337

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import queue
INF = 1<<30
str = input().split()
n = int(str[0])
m = int(str[1])
min_cost = [INF] * (n+1)
node = []
for i in range(n+1):
node.append([])
for i in range(m):
str = input().split()
a = int(str[0])
b = int(str[1])
cost = int(str[2])
node[a].append((b,cost))
node[b].append((a,cost))
pq = queue.PriorityQueue()
pq.put((0,1))
while not pq.empty():
now = pq.get()
cost = now[0]
pos = now[1]
if cost <= min_cost[pos]:
for next in node[pos]:
to = next[0]
ncost = next[1] + cost
if ncost < min_cost[to]:
min_cost[to] = ncost
pq.put((ncost,to))
if min_cost[n] == INF:
print("NA")
else :
print(min_cost[n])

ステータス

項目 データ
問題 0431 - 君も始めようダイクストラ大好き厨
ユーザー名 ei1630
投稿日時 2019-06-09 18:29:38
言語 Python3
状態 Accepted
得点 1
ソースコード長 782 Byte
最大実行時間 1068 ms
最大メモリ使用量 42972 KB

セット

セット 得点 Cases
1 ALL 1 / 1 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
m_in1.txt AC 1068 ms 42972 KB
1
r_in1.txt AC 232 ms 11500 KB
1
r_in2.txt AC 261 ms 11872 KB
1
r_in3.txt AC 268 ms 12312 KB
1
r_in4.txt AC 121 ms 10216 KB
1
r_in5.txt AC 349 ms 13628 KB
1
r_in6.txt AC 315 ms 13752 KB
1
r_in7.txt AC 153 ms 8284 KB
1
r_in8.txt AC 170 ms 8752 KB
1
r_in9.txt AC 371 ms 15664 KB
1
r_in10.txt AC 76 ms 7776 KB
1
r_in11.txt AC 229 ms 11084 KB
1
r_in12.txt AC 250 ms 11360 KB
1
r_in13.txt AC 265 ms 11776 KB
1
r_in14.txt AC 275 ms 12324 KB
1
r_in15.txt AC 282 ms 12692 KB
1
r_in16.txt AC 122 ms 10528 KB
1
r_in17.txt AC 110 ms 10876 KB
1
r_in18.txt AC 124 ms 11220 KB
1
r_in19.txt AC 124 ms 7620 KB
1
r_in20.txt AC 149 ms 8704 KB
1
r_in21.txt AC 97 ms 6424 KB
1
r_in22.txt AC 116 ms 7032 KB
1
r_in23.txt AC 129 ms 7488 KB
1
r_in24.txt AC 142 ms 7976 KB
1
r_in25.txt AC 184 ms 8900 KB
1
r_in26.txt AC 174 ms 9340 KB
1
r_in27.txt AC 208 ms 9856 KB
1
r_in28.txt AC 212 ms 10112 KB
1
r_in29.txt AC 219 ms 10616 KB
1
r_in30.txt AC 237 ms 11080 KB
1