测评机： Xeost[5]
得分： 90分
提交日期： 2008-11-14 16:10:00
有效耗时： 2390毫秒
测试结果1: 通过本测试点|有效耗时172:ms
测试结果2: 通过本测试点|有效耗时172:ms
测试结果3: 通过本测试点|有效耗时171:ms
测试结果4: 通过本测试点|有效耗时188:ms
测试结果5: 通过本测试点|有效耗时234:ms
测试结果6: 通过本测试点|有效耗时344:ms
测试结果7: 通过本测试点|有效耗时281:ms
测试结果8: 通过本测试点|有效耗时250:ms
测试结果9: 通过本测试点|有效耗时578:ms
测试结果10: 选手程序运行超过时限
program pp；
var
x,y,z:array[1..300000] of longint；
aim :array[1..30000] of longint；
final:array[1..30000] of longint；
d :array[1..30000] of longint；
line :array[1..300000] of longint；
n,m:longint；
procedure quick(l,r:longint)；
var
i,j,w,p:longint；
begin
i:=l； j:=r；
w:=x[i+random(j-i+1)]；
repeat
while x[i]<w do inc(i)；
while w<x[j] do dec(j)；
if i<=j then
begin
p:=x[i]； x[i]:=x[j]； x[j]:=p；
p:=y[i]； y[i]:=y[j]； y[j]:=p；
p:=z[i]； z[i]:=z[j]； z[j]:=p；
inc(i)； dec(j)；
end；
until i>j；
if l<j then quick(l,j)；
if i<r then quick(i,r)；
end；
procedure init；
var
i:longint；
begin
read(n,m)；
for i:=1 to m do
begin
read(x[i],y[i],z[i])；
x[m+i]:=y[i]；
y[m+i]:=x[i]；
z[m+i]:=z[i]；
end；
quick(1,m*2)；
aim[x[1]]:=1；
for i:=2 to m*2 do if x[i]<>x[i-1] then
begin
aim[x[i]]:=i；
final[x[i-1]]:=i-1；
end；
end；
procedure SPFA；
var
i,l,r:longint；
begin
fillchar(d,sizeof(d),$7f)；
l:=0； r:=1；
line[1]:=1；
d[1]:=0；
while l<r do
begin
inc(l)；
for i:=aim[line[l]] to final[line[l]] do
begin
if d[line[l]]+z[i]<d[y[i]] then
begin
d[y[i]]:=d[line[l]]+z[i]；
inc(r)；
line[r]:=y[i]；
end；
end；
end；
write(d[n])；
end；
begin
init；
SPFA；
end.