type rr=record

x,y,z:integer;

end;

var a:array[1..maxn]of rr;

st,ed:array[1..30000]of integer;

dis:array[1..30000]of longint;

l:array[1..30000]of integer;

p:array[1..30000]of boolean;

min,m,h,t:longint;

i,j,n,k:integer;

procedure qsort(i,j:integer);

var l,r,s:integer;k:rr;

begin

l:=i;r:=j;s:=a[l].x;

repeat

while a[l].x<s do inc(l);

while a[r].x>s do dec(r);

if l<=r then

begin

k:=a[l];a[l]:=a[r];a[r]:=k;inc(l);dec(r);

end;

until l>r;

if i<r then qsort(i,r);

if l<j then qsort(l,j);

end;

begin

readln(n,m);

for i:=1 to m do

begin

read(a[i].x,a[i].y,a[i].z);

a[i+m].x:=a[i].y;a[i+m].y:=a[i].x;a[i+m].z:=a[i].z

end;

qsort(1,m*2);

for i:=1 to m*2 do ed[a[i].x]:=i;

for i:=m*2 downto 1 do st[a[i].x]:=i;

fillchar(dis,sizeof(dis),$7f);

fillchar(p,sizeof(p),false);

h:=0;t:=1;l[1]:=1; dis[1]:=0;p[1]:=true;

repeat

inc(h);

for i:=st[l[h]] to ed[l[h]] do

if dis[l[h]]+a[i].z<dis[a[i].y] then

begin

dis[a[i].y]:=dis[l[h]]+a[i].z;

if not(p[a[i].y]) then

begin

inc(t);l[t]:=a[i].y;p[a[i].y]:=true;

end;

end;

p[l[h]]:=false;

until h>=t;

writeln(dis[n]);

end.

测试结果1: 通过本测试点|有效耗时 172ms

测试结果2: 通过本测试点|有效耗时156ms

测试结果3: 通过本测试点|有效耗时172ms

测试结果4: 通过本测试点|有效耗时188ms

测试结果5: 通过本测试点|有效耗时234ms

测试结果6: 输出过长|用户输出数据超过标准输出两倍[标准输出4位|选手输出10位]

测试结果7: 运行错误|普通保护错误

测试结果8: 运行错误|普通保护错误

测试结果9: 输出过长|用户输出数据超过标准输出两倍[标准输出4位|选手输出10位]

测试结果10: 输出过长|用户输出数据超过标准输出两倍[标准输出4位|选手输出10位]

测试结果7: 运行错误|普通保护错误

测试结果8: 运行错误|普通保护错误

这个是什么意思？