讨论 / 求解 为什么不能够
wsxtyrdd 2012-07-18 17:59:00
点我顶贴 收藏 删除
这一题所有的数据都是不能在起点和终点买卖的

为什么

求大牛解释 ~~~~~~

只要不在起点和终点买卖就AC

要不就WA 0 答案全99 为什么~~~~

#1 wsxtyrdd@2012-07-05 01:50:00
回复 删除
题目:[NOIP09]最优贸易

状态: Accepted

测评机: Xeost[5]

得分: 100分 [我要评价一下题目~]

提交日期: 2012-7-5 16:33:00

有效耗时: 2750毫秒

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

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

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

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

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

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

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

测试结果8: 通过本测试点|有效耗时265ms

测试结果9: 通过本测试点|有效耗时454ms

测试结果10: 通过本测试点|有效耗时421ms

提交代码: view sourceprint?001.var n,max,min,m,i,j,t,s,r:longint;

002.

a,b,c:array[0..800000]of longint;

003.

q,f,d,w,p:array[0..100000] of longint;

004.

flag:array[0..100000]of boolean;

005.procedure qsort(l,r:longint);

006.var ll,rr,tt,mid:longint;

007.begin

008.ll:=l;

009.rr:=r;

010.mid:=a[(l+r) div 2];

011.repeat

012.while a[ll]<mid do inc(ll);

013.while a[rr]>mid do dec(rr);

014.if ll<=rr then

015.begin

016.tt:=a[ll];a[ll]:=a[rr];a[rr]:=tt;

017.tt:=b[ll];b[ll]:=b[rr];b[rr]:=tt;

018.inc(ll);

019.dec(rr);

020.end

021.until ll>rr;

022.if ll<r then qsort(ll,r);

023.if rr>l then qsort(l,rr);

024.end;

025.function relax(u,v:longint):boolean;

026.begin

027.if d[u]+c[v]<d[b[v]] then

028.begin

029.d[b[v]]:=d[u]+c[v];

030.exit(true);

031.end

032.else exit(false);

033.end;

034.procedure spfa(x:longint);

035.var v,ss,tt,h:longint;

036.begin

037.tt:=1;

038.ss:=x;

039.fillchar(q,sizeof(q),0);

040.fillchar(flag,sizeof(flag),false);

041.fillchar(d,sizeof(d),127);

042.d[ss]:=0;

043.flag[ss]:=true;

044.q[1]:=ss;

045.while h<>tt do

046.begin

047.h:=h mod n+1;

048.v:=q[h];

049.flag[v]:=false;

050.for i:=f[v] to f[v+1]-1 do

051.if relax(v,i) then

052.if flag[b[i]]=false then

053.begin

054.tt:=tt mod n+1;

055.q[tt]:=b[i];

056.flag[b[i]]:=true;

057.end;

058.end;

059.end;

060.begin

061.read(n,m);

062.for i:=1 to n do

063.read(w[i]);

064.for i:=1 to m do

065.begin

066.read(a[i],b[i],s);

067.if s=2 then

068.begin

069.inc(t);

070.a[m+t]:=b[i];

071.b[m+t]:=a[i];

072.c[m+t]:=1;

073.end;

074.c[i]:=1;

075.end;

076.m:=m+t;

077.qsort(1,m);

078.for i:=1 to m do

079.if f[a[i]]=0 then f[a[i]]:=i;

080.f[n+1]:=m+1;

081.for i:=n downto 1 do

082.if f[i]=0 then f[i]:=f[i+1];

083.spfa(1);

084.for i:=1 to n do

085.p[i]:=d[i];

086.for i:=1 to m do

087.begin t:=b[i];b[i]:=a[i];a[i]:=t; end;

088.qsort(1,m);

089.for i:=1 to n do

090.f[i]:=0;

091.for i:=1 to m do

092.if f[a[i]]=0 then f[a[i]]:=i;

093.f[n+1]:=m+1;

094.for i:=n downto 1 do

095.if f[i]=0 then f[i]:=f[i+1];

096.spfa(n);

097.r:=0;

098.min:=maxlongint;

099.for i:=2 to n-1 do

100.if (d[i]<10000)and(p[i]<10000) then

101.begin

102.if w[i]>max then max:=w[i];

103.if w[i]<min then min:=w[i];

104.end;

105.write(max-min);

106.end.

#2 wsxtyrdd@2012-07-05 01:51:00
回复 删除
只要 把99行的 for i:=2 to n-1 do

改成 for i:=1 to n do

就全WA 输出99 为什么?????

#3 gzyxs@2012-07-16 20:21:00
回复 删除
只要 把99行的 for i:=2 to n-1 do

改成 for i:=1 to n do

#4 wsxtyrdd@2012-07-18 17:59:00
回复 删除
没人回复啊

当撒分+RP了

查看更多回复
提交回复