[quote][url=/Redirect.asp?Act=Reply&DID=11565&RID=28334]原帖[/url]由 [i]wwwaaannngggrs[/i] 于 2012-10-3 9:12:00 发表
rt[/quote]
跪了……链式前向星spfa50000都超时了诶……
然后就是这题确实卡spfa...但是问题主要是rq的机器是越来越慢了= =
spfa有一个常数优化 就是如果扩展的点dist小于队头的dist就从前面进队,否则从后面进队.
因题而异...........这个可以稍微减少点扩展点数,但是每次判断的常数大了一些.....所以斟酌使用吧..
这题可以这样写没问题 能过..
再次吐槽一下rq的机器越来越慢了.......
要是还是不能过就io优化吧.....
状态: Accepted
测评机： Xeost[5]
得分： 100分 [我要评价一下题目~]
提交日期： 2012-9-29 23:46:00
有效耗时： 3248毫秒
测试结果1: 通过本测试点|有效耗时234ms
测试结果2: 通过本测试点|有效耗时234ms
测试结果3: 通过本测试点|有效耗时203ms
测试结果4: 通过本测试点|有效耗时203ms
测试结果5: 通过本测试点|有效耗时203ms
测试结果6: 通过本测试点|有效耗时203ms
测试结果7: 通过本测试点|有效耗时484ms
测试结果8: 通过本测试点|有效耗时484ms
测试结果9: 通过本测试点|有效耗时485ms
测试结果10: 通过本测试点|有效耗时515ms
提交代码： view sourceprint?001.type
002.
node=record
003.
x,y,next:longint;
004.
end;
005.var
006.
a,dis,len,heap,pos:array [1..1000000] of longint;
007.
b:array [1..500000] of node;
008.
n,m,tot:longint;
009.procedure ins(x,y,z:longint);
010.begin
011.
inc(tot);
012.
b[tot].x:=y;
013.
b[tot].y:=z;
014.
b[tot].next:=a[x];
015.
a[x]:=tot;
016.end;
017.procedure init;
018.var
019.
i,x,y,z:longint;
020.begin
021.
readln(n,m);
022.
fillchar(a,sizeof(a),0);
023.
tot:=0;
024.
for i:=1 to m do
025.
begin
026.
readln(x,y,z);
027.
ins(x,y,z);
028.
ins(y,x,z);
029.
end;
030.
fillchar(len,sizeof(len),0);
031.
for i:=1 to n do
032.
begin
033.
heap[i]:=i;
034.
pos[i]:=i;
035.
end;
036.end;
037.procedure swap(var x,y:longint);
038.var
039.
t:longint;
040.begin
041.
t:=x;
042.
x:=y;
043.
y:=t;
044.end;
045.procedure up(l:longint);
046.begin
047.
while l>1 do
048.
begin
049.
if (dis[heap[l]]>dis[heap[l div 2]]) or ((dis[heap[l]]=dis[heap[l div 2]]) and (len[heap[l]]>len[heap[l div 2]])) then break;
050.
swap(pos[heap[l]],pos[heap[l div 2]]);
051.
swap(heap[l],heap[l div 2]);
052.
l:=l div 2;
053.
end;
054.end;
055.procedure down(l:longint);
056.begin
057.
while l*2<=tot do
058.
begin
059.
l:=l*2;
060.
if l<tot then
061.
if (dis[heap[l]]>dis[heap[l+1]]) or ((dis[heap[l]]=dis[heap[l+1]]) and (len[heap[l]]>len[heap[l+1]])) then inc(l);
062.
if (dis[heap[l]]>dis[heap[l div 2]]) or ((dis[heap[l]]=dis[heap[l div 2]]) and (len[heap[l]]>len[heap[l div 2]])) then break;
063.
swap(pos[heap[l]],pos[heap[l div 2]]);
064.
swap(heap[l],heap[l div 2]);
065.
end;
066.end;
067.procedure heap_dijkstra;
068.var
069.
i,j,k,p,pp,t,dist:longint;
070.begin
071.
fillchar(dis,sizeof(dis),$7f);
072.
dis[1]:=0; tot:=n;
073.
while tot>0 do
074.
begin
075.
t:=heap[1];
076.
dist:=dis[t];
077.
swap(pos[heap[1]],pos[heap[tot]]);
078.
swap(heap[1],heap[tot]);
079.
dec(tot);
080.
down(1);
081.
p:=a[t];
082.
while p<>0 do
083.
begin
084.
pp:=b[p].x;
085.
if (dist+b[p].y<dis[pp]) or ((dist+b[p].y=dis[pp]) and (len[t]+1<len[pp])) then
086.
begin
087.
dis[pp]:=dist+b[p].y;
088.
len[pp]:=len[t]+1;
089.
up(pos[pp]);
090.
end;
091.
p:=b[p].next;
092.
end;
093.
end;
094.
writeln(dis[n],' ',len[n]);
095.end;
096.begin
097.
init;
098.
heap_dijkstra;
099.end.
Powered By RenQing | Developping By Wish Azuis 帮助 关于
鲁ICP备05014231号
Processed in 0.078125 second(s). Copyright (c) 2007-2009 Www.RQNOJ.Cn. All Rights Reserved .