const max=100000;
var
i,j,n,m,z,y,x:longint;
a,b,e,f:array[1..300000] of longint;
p:array[1..300000] of longint;
procedure swap(x,y:longint);
var
s:longint;
begin
s:=a[x];
a[x]:=a[y];
a[y]:=s;
s:=b[x];
b[x]:=b[y];
b[y]:=s;
s:=e[x];
e[x]:=e[y];
e[y]:=s;
end;
procedure qsort(top,tail:longint);
var
x1,x2,x3,i,j:longint;
begin
i:=top;
j:=tail;
x1:=a[i];
x2:=b[i];
x3:=e[i];
while i<j do
begin
while (i<j)and(a[j]>=x1) do dec(j);
swap(i,j);
while (i<j)and(a[i]<=x1) do inc(i);
swap(i,j);
end;
a[i]:=x1;
b[i]:=x2;
e[i]:=x3;
if top<i-1 then qsort(top,i-1);
if i+1<tail then qsort(i+1,tail);
end;
procedure SPFA;
var
i,j,top,tail,x,k:longint;
v:array[1..300000] of boolean;
aa:array[1..1000000] of longint;
begin
top:=0;
tail:=1;
for i:=1 to n do
p[i]:=max;
fillchar(v,sizeof(v),false);
v[1]:=true;
aa[1]:=1;
p[1]:=0;
while top<tail do
begin
inc(top);
x:=aa[top];
for i:=f[x] to f[x+1]-1 do
begin
k:=b[i];
if p[x]+e[i]<p[k] then
begin
p[k]:=p[x]+e[i];
if not(v[k]) then
begin
inc(tail);
aa[tail]:=k;
v[k]:=true;
end;
end;
end;
v[x]:=false;
end;
end;
begin
readln(n,m);
for i:=1 to m do
begin
readln(x,y,z);
a[i]:=x;
b[i]:=y;
e[i]:=z;
a[i+m]:=y;
b[i+m]:=x;
e[i+m]:=z;
end;
qsort(1,m*2);
for i:=1 to m*2 do
if f[a[i]]=0 then f[a[i]]:=i;
f[n+1]:=m*2+1;
for i:=n downto 1 do
if f[i]=0 then f[i]:=f[i+1];
SPFA;
write(p[n]);
end.
状态: Accepted
测评机： Xeond[6]
得分： 100分
提交日期： 2010-11-17 10:38:00
有效耗时： 3422毫秒
测试结果1: 通过本测试点|有效耗时172ms
测试结果2: 通过本测试点|有效耗时157ms
测试结果3: 通过本测试点|有效耗时187ms
测试结果4: 通过本测试点|有效耗时188ms
测试结果5: 通过本测试点|有效耗时234ms
测试结果6: 通过本测试点|有效耗时344ms
测试结果7: 通过本测试点|有效耗时297ms
测试结果8: 通过本测试点|有效耗时265ms
测试结果9: 通过本测试点|有效耗时578ms
测试结果10: 通过本测试点|有效耗时1000ms
对这题的数据表示压力很大。。你最后一个点是多少啊
这题只得了90分
最后一点超时。。。。。。。。。。。。
2531毫秒
测试结果1: 通过本测试点|有效耗时156ms
测试结果2: 通过本测试点|有效耗时157ms
测试结果3: 通过本测试点|有效耗时171ms
测试结果4: 通过本测试点|有效耗时204ms
测试结果5: 通过本测试点|有效耗时250ms
测试结果6: 通过本测试点|有效耗时359ms
测试结果7: 通过本测试点|有效耗时312ms
测试结果8: 通过本测试点|有效耗时266ms
测试结果9: 通过本测试点|有效耗时656ms
测试结果10: 选手程序运行超过时限