Submission #09632

ソースコード

?
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
import Queue as Q
que=Q.PriorityQueue(-1)
l=map(int,raw_input().split())
n=l[0]
m=l[1]
road=[]
minc=[]
f=0
for var in range(0,n+1):
road.append([])
minc.append(1<<30)
for var in range(0,m):
l=map(int,raw_input().split())
a=l[0]
b=l[1]
c=l[2]
a=a-1
b=b-1
road[a].append([b,c])
road[b].append([a,c])
que.put([0,0])
while not que.empty():
now=que.get()
if(now[1]==n-1):
print now[0]
f=1
break
for var in road[now[1]]:
if minc[var[0]]>now[0]+var[1]:
minc[var[0]]=now[0]+var[1]
que.put([now[0]+var[1],var[0]])
if f==0: print "NA" ]]>

ステータス

項目 データ
問題 0431 - 君も始めようダイクストラ大好き厨
ユーザー名 ei1417
投稿日時 2016-09-15 18:35:08
言語 Python2
状態 Accepted
得点 1
ソースコード長 609 Byte
最大実行時間 1210 ms
最大メモリ使用量 52540 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
m_in1.txt AC 1210 ms 52540 KB
1
r_in1.txt AC 156 ms 13796 KB
1
r_in2.txt AC 160 ms 17216 KB
1
r_in3.txt AC 193 ms 19792 KB
1
r_in4.txt AC 97 ms 16972 KB
1
r_in5.txt AC 249 ms 22140 KB
1
r_in6.txt AC 190 ms 21472 KB
1
r_in7.txt AC 105 ms 15324 KB
1
r_in8.txt AC 112 ms 15988 KB
1
r_in9.txt AC 157 ms 23780 KB
1
r_in10.txt AC 76 ms 8976 KB
1
r_in11.txt AC 166 ms 13404 KB
1
r_in12.txt AC 126 ms 13640 KB
1
r_in13.txt AC 214 ms 15092 KB
1
r_in14.txt AC 221 ms 16004 KB
1
r_in15.txt AC 193 ms 16748 KB
1
r_in16.txt AC 70 ms 13764 KB
1
r_in17.txt AC 81 ms 14392 KB
1
r_in18.txt AC 91 ms 15252 KB
1
r_in19.txt AC 78 ms 11744 KB
1
r_in20.txt AC 92 ms 13596 KB
1
r_in21.txt AC 58 ms 10516 KB
1
r_in22.txt AC 65 ms 11176 KB
1
r_in23.txt AC 71 ms 12032 KB
1
r_in24.txt AC 86 ms 12692 KB
1
r_in25.txt AC 133 ms 14056 KB
1
r_in26.txt AC 108 ms 14708 KB
1
r_in27.txt AC 145 ms 15540 KB
1
r_in28.txt AC 126 ms 16336 KB
1
r_in29.txt AC 159 ms 17008 KB
1
r_in30.txt AC 165 ms 18188 KB
1