WA6. What's wrong? Give some test's. In my solution I used Deixtra algo.

Why Dijkstra?
Simple dfs for topsort and then dp.

I think this problem could not be solved with dijkstra.
Simple dfs for topsort and then dp or simple BFS :)

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

Edited by author 16.04.2008 22:55

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(((