讨论 / 请问c++里面为什么不能在一个printf里面先输出个%lld再输出个%d……
fts96 2012-10-09 13:45:00
点我顶贴 收藏 删除
顺便问一句此题为何卡spfa……
#1 wwwaaannngggrs@2012-10-03 09:12:00
回复 删除
我没卡啊。。。我真的没有故意卡啊。。。

rt

#2 fts96@2012-10-04 09:26:00
回复 删除
额……难道是我写了好久的spfa是错的……

[quote][url=/Redirect.asp?Act=Reply&DID=11565&RID=28334]原帖[/url]由 [i]wwwaaannngggrs[/i] 于 2012-10-3 9:12:00 发表

rt[/quote]

跪了……链式前向星spfa50000都超时了诶……

#3 遗忘de国度@2012-10-04 12:57:00
回复 删除
目测"%I64d %d"毫无问题

然后就是这题确实卡spfa...但是问题主要是rq的机器是越来越慢了= =

spfa有一个常数优化 就是如果扩展的点dist小于队头的dist就从前面进队,否则从后面进队.

因题而异...........这个可以稍微减少点扩展点数,但是每次判断的常数大了一些.....所以斟酌使用吧..

这题可以这样写没问题 能过..

再次吐槽一下rq的机器越来越慢了.......

要是还是不能过就io优化吧.....

#4 工藤柯南@2012-10-09 13:45:00
回复 删除
题目:shortest

状态: 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 .

查看更多回复
提交回复