Submission #49926

ソースコード

?
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]
for i in range(len(node[pos])):
next = node[pos][i][0]
ncost = node[pos][i][1] + cost
if ncost < min_cost[next] :
min_cost[next] = ncost
pq.put((ncost,next))
if min_cost[n] == INF :
print('NA')
else :
print(min_cost[n])

ステータス

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

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
m_in1.txt AC 1260 ms 44388 KB
1
r_in1.txt AC 267 ms 13176 KB
1
r_in2.txt AC 320 ms 16120 KB
1
r_in3.txt AC 292 ms 18672 KB
1
r_in4.txt AC 117 ms 16992 KB
1
r_in5.txt AC 357 ms 20792 KB
1
r_in6.txt AC 317 ms 21036 KB
1
r_in7.txt AC 168 ms 15688 KB
1
r_in8.txt AC 178 ms 16280 KB
1
r_in9.txt AC 434 ms 23564 KB
1
r_in10.txt AC 83 ms 9576 KB
1
r_in11.txt AC 256 ms 13136 KB
1
r_in12.txt AC 305 ms 13788 KB
1
r_in13.txt AC 286 ms 14584 KB
1
r_in14.txt AC 295 ms 15524 KB
1
r_in15.txt AC 315 ms 16152 KB
1
r_in16.txt AC 107 ms 14096 KB
1
r_in17.txt AC 123 ms 14832 KB
1
r_in18.txt AC 122 ms 15276 KB
1
r_in19.txt AC 172 ms 11348 KB
1
r_in20.txt AC 185 ms 13332 KB
1
r_in21.txt AC 114 ms 11044 KB
1
r_in22.txt AC 130 ms 11780 KB
1
r_in23.txt AC 134 ms 12244 KB
1
r_in24.txt AC 165 ms 12864 KB
1
r_in25.txt AC 197 ms 13904 KB
1
r_in26.txt AC 195 ms 14596 KB
1
r_in27.txt AC 205 ms 15208 KB
1
r_in28.txt AC 228 ms 15840 KB
1
r_in29.txt AC 274 ms 16592 KB
1
r_in30.txt AC 261 ms 17724 KB
1