|
|
back to boardWA6 WA6. What's wrong? Give some test's. In my solution I used Deixtra algo. Re: WA6 Why Dijkstra? Simple dfs for topsort and then dp. Re: WA6 I think this problem could not be solved with dijkstra. Simple dfs for topsort and then dp or simple BFS :) Re: WA6 Posted by Rustam 16 Apr 2008 21:36 i used FLOYD's algo and have TLE15. i used Djkstra's algo and i have WA10.. pls, can you give me some tests or what's bug in my program? {$APPTYPE CONSOLE} uses SysUtils; var a:array [1..1000,1..1000] of longint; mas:array [1..1000] of longint; used:array [1..1000] of boolean; i,n,m,t,f:longint; procedure djkstra(st:longint); var cur,i:longint; begin fillchar(mas,sizeof(mas),255); fillchar(used,sizeof(used),0); cur:=st; mas[cur]:=0; repeat used[cur]:=true; for i:=1 to n do if (a[cur,i]<>0) and (mas[i]<mas[cur]+a[cur,i]) then mas[i]:=mas[cur]+a[cur,i]; cur:=0; for i:=1 to n do if not used[i] and (mas[i]<>-1)and ((cur=0)or (mas[cur]>mas[i])) then cur:=i; until cur=0; end; begin read(n,m); for i:=1 to m do begin read(t,f); read(a[t,f]); end; read(t,f); djkstra(t); if mas[f]<>-1 then write(mas[f]) else write('No solution'); halt(0); end. and what to do if there is cycle? Edited by author 16.04.2008 21:52 Edited by author 16.04.2008 21:56 Re: WA6 Posted by awpris 16 Apr 2008 22:52 Edited by author 16.04.2008 22:55 Re: WA6 Posted by Rustam 8 Jul 2008 00:32 i've changed djkstra like this <code>procedure djkstra(x:longint); var cur,i:longint; begin fillchar(v,sizeof(v),-1); fillchar(used,sizeof(used),0); v[x]:=0; cur:=x; repeat used[cur]:=true; for i:=1 to n do if (a[cur,i]<>0) and ((v[i]=-1)or (v[i]<v[cur]+a[cur,i])) then begin v[i]:=v[cur]+a[cur,i]; used[i]:=false; end; cur:=0; for i:=1 to n do if not used[i] and (v[i]<>-1)and((cur=0)or (v[cur]<v[i])) then cur:=i; until cur =0; end;</code> and it's tle#15((( |
|
|