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: 运行错误|普通保护错误
这个是什么意思?
const maxn=300000;
maxm=30000;
max=20000;
type rr=record
x,y,z:integer;
end;
var a:array[1..maxn]of rr;
st,ed:array[1..maxm]of longint;
dis:array[1..maxm]of longint;
l:array[1..max]of integer;
p:array[1..maxm]of boolean;
m,h,t,i,j:longint;
n:integer;
procedure qsort(i,j:longint);
var l,r:longint;k:rr;s:integer;
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;
for i:=1 to n do
begin dis[i]:=maxlongint;p[i]:=false;end;
h:=0;t:=1;l[1]:=1; dis[1]:=0;p[1]:=true;
repeat
inc(h); if h>max then h:=1;
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);if t>max then t:=1;l[t]:=a[i].y;p[a[i].y]:=true;end;
end;
p[l[h]]:=false;
until h>=t;
writeln(dis[n]);
end.
过了8个。。数据类型不够大
测试结果1: 通过本测试点|有效耗时 156ms
测试结果2: 通过本测试点|有效耗时157ms
测试结果3: 通过本测试点|有效耗时171ms
测试结果4: 通过本测试点|有效耗时204ms
测试结果5: 通过本测试点|有效耗时250ms
测试结果6: 通过本测试点|有效耗时359ms
测试结果7: 通过本测试点|有效耗时297ms
测试结果8: 通过本测试点|有效耗时265ms
测试结果9: 输出过长|用户输出数据超过标准输出两倍[标准输出4位|选手输出10位]
测试结果10: 选手程序运行超过时限