ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1450. Russian Pipelines

WA6
Posted by Kirin Vladislav 26 Feb 2007 11:59
WA6. What's wrong? Give some test's. In my solution I used Deixtra algo.
Re: WA6
Posted by Anton [SUrSU] 26 Feb 2007 14:25
Why Dijkstra?
Simple dfs for topsort and then dp.
Re: WA6
Posted by @ntiFreeze 27 Feb 2007 00:57
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(((