- -膜拜楼下神cow小马甲!!!

dijkstra+堆 or Fibonacci优化=0ms

虽说普通的dijkstra碰到好的评测机也可以秒杀...

囧题。。

对LS无语

才提交 11 次就 AC 了, 乐死我了！

P.S. 庆祝 2 星半 :)

const size=1000;

var

a:array[0..size,0..size] of longint;

d,f:array[0..size] of longint;

q:array[1..3*size] of longint;

v:array[0..size] of boolean;

i,j,h,t,n:longint;

procedure print(i:longint);

begin

if i=0 then exit;

print(f[i]);

write(i, ' ');

end;

begin

readln(n);

for i:=1 to n do

begin

for j:=1 to n do

read(a);

readln;

end;

fillchar(d,sizeof(d),$76);

fillchar(v,sizeof(v),false);

d[1]:=0;

f[1]:=0;

h:=1;

t:=2;

q[t]:=1;

v[1]:=true;

while h

编译通过...

├ 测试数据 01：答案正确... 25ms

├ 测试数据 02：答案正确... 228ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 181ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 166ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 56ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：656ms

好慢啊

简单的动态规划！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var i,j,n:longint;

used:array[0..1000]of boolean;

a:array[0..1001,0..1001]of longint;

route:array[0..1001]of longint;

procedure find(v:longint);

begin

if v=1 then write(v,' ')

else

begin

find(route[v]);

write(v,' ');

end;

end;

procedure dijkstra;

var t,i,min,minn:longint;

begin

used[1]:=true;

for i:=1 to n do route[i]:=1;

for t:=1 to n-1 do

begin

min:=99999999;

minn:=0;

for i:=2 to n do if not(used[i])and(a[1,i]

纯水题...不过这时间不好看》。。。。

---|---|---|---|---|---|---|---|---|---|-

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 228ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 197ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 134ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 150ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：709ms

var n:longint;map:array[0..1000,0..1000]of longint;rout,dis:array[0..1000]of longint; v:array[0..1000]of boolean;procedure init; var i,j:longint;begin readln(n); for i:=1 to n do begin for j:=1 to n do begin read(map); end; readln; end; end;procedure djstra; var s,g,i,min,t:longint;begin for i:=1 to n do dis[i]:=10000000; fillchar(v,sizeof(v),0); s:=1; dis[1]:=0; rout[1]:=0; v[1]:=true; for g:=1 to n-1 do begin min:=10000000; for i:=1 to n do begin if not(v[i]) then if (map0)and(map+dis

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9ms

program ex;

var

n,i,i1:longint;

a:packed array[1..1000,1..1000]of longint;

min:array[1..1000]of longint;

minl:packed array[1..1000]of ansistring;

q:string;

begin

readln(n);

minl[1]:='1';

for i:=2 to n do

min[i]:=1000000000;

for i:=1 to n do begin

for i1:=1 to n do

read(a);

readln;end;

for i:=1 to n do

for i1:=i+1 to n do

if (a>0)and(min[i1]>min[i]+a) then begin

min[i1]:=min[i]+a;

str(i1,q);

minl[i1]:=minl[i]+' '+q;end;

writeln(minl[n]);

write(min[n]);

end.

....这最短路也太裸了吧~~看了样例就晓得了 （加个记录）

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 41ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：41ms

├ 测试数据 01：答案正确... 72ms

├ 测试数据 02：答案正确... 369ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 338ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 291ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 259ms

数组开大一点就过了,为什么这么慢`- -

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 9ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：43ms

const

maxn=1000;

var

cost:array[1..maxn,1..maxn] of longint;

a,path,way:array[1..maxn] of integer;

x,y,z,n,k,i,s,t,j,p,m:integer;

mark:array[1..maxn] of boolean;

procedure readdata;

var i,j:integer;

begin

readln(n);

for i:=1 to n do

for j:=1 to n do

cost:=maxint;

for i:=1 to n do

begin

for j:=1 to n do

begin

read(z);

if (z-1) and (z0) then

cost:=z;

end;

readln;

end;

end;

procedure dijkstra;

var i,j,min,minj,temp:integer;

begin

fillchar(mark,sizeof(mark),false);

for i:=1 to n do

begin

a[i]:=cost;

path[i]:=s;

end;

a:=0;

mark:=true;

path:=0;

for i:=2 to n do

begin

min:=maxint;

for j:=1 to n do

if (not(mark[j])) and (a[j]

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 9ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：43ms

最短路也不用出的这么裸吧？？

怎么这么慢！！！！！！！

不过好歹是10分钟搞定的！

├ 测试数据 01：答案正确... 212ms

├ 测试数据 02：答案正确... 791ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 775ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 650ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 9ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 588ms

很BT的搜索哦

var i,j,n,m,k,l,o,p,min:longint;

r,s:ansistring;

a:array[0..1000,0..1000] of longint;

procedure try(q,w:longint;e:ansistring);

var i,j:longint;

begin

if q=n then

begin

if w=min then exit;

for i:=n downto 1 do

begin

if a[q,i]>0 then

begin

str(i,s);

try(i,w+a[q,i],e+' '+s);

end;

end;

end;

begin

readln(n);

for i:=1 to n do

begin

for j:=1 to n do

read(a);

end;

min:=maxlongint;

try(1,0,'1');

writeln(r);

writeln(min);

end.

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 291ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 244ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 197ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 166ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：898ms

FLOYED的n^2版。。。

{ i:=1;

for k:=1 to n do

for j:=1 to n do begin

}

超简单。。。

.................

算了...水题...算作练习背诵好了

SPFA:

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 41ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：75ms

Bellman-Ford:

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 9ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 25ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 9ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：43ms

Floyd-Warshall:

编译通过...

├ 测试数据 01：答案正确... 884ms

├ 测试数据 02：运行超时...

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：运行超时...

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：运行超时...

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 72ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：运行超时...

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：60 有效耗时：956ms