OJ Board

Build your paths matrix (as you did) then use a modified Floyd Warshall to remove cycles.

ie Also, remove the constraints from your path building section (i!=k) it just messes things up. I would do this instead:

It has to do with your pruning methods. You are not removing all the nodes along all the cycles. In fact, I could only find 1 test case where this failed, and even then it was only 1 element of the matrix that was off.

About the constraints (i!=k): You can safely ignore these constraints.

Mine was O(n^3). What I did was use Floyd-Warshall and then I used it again..

I'm not sure why your algorithm is O(n^6) but you can split them up and get into 2 parts that each runs in O(n^3) time.
O(n^3) time to run Floyd to find the number of paths,
O(n^3) time to find cycles.
Then for each (u, v), if the second part reports a cycle print -1, else print the number of paths found in part 1...

Hope this helps.

You are correct junjieliang. It was my mistake. My program is actually O(N^3). I should have thought a bit more before I started typing.

My program does exactly what you specified. Of course, my stupid mistake was saying that n^3 + n^3 == n^6

Thanks!

I am having trouble with this problem. getting WA. please help me
here is my code:
[c]removed[/c]

Graphs in input can be multigraphs ....

Best regards
DM

finally got AC. the bug is in my findpath function.

anyway, Dominik, what do u mean by

Graphs in input can be multigraphs ....

please, expain.

That means that input could be in form of:
I don't remember exact format, so I write idea only ...)
1->2
1->3
1->2
....
so from 1 to 2 exist two paths, not one ....

Best regards
DM

PS. This is my mistake, when I try to solve this problem

thanks, Dominik.
but I think I didn't handle the case (same input more than once) but got AC.

Maybe test cases doesn't contian such cases or you have 'mistake' in your code such that you got correct answer I don't know ...
But I remember, that I found some IO in net from original contest and such cases were there. So I think, that probably exists in judge data. BTW.I got Acc when I handle multigraphs:-)

Best regards
DM

Is there any special or tricky input to consider ?

In all cities, intersections are numbered sequentially from 0 to the ``largest'' intersection

It means that if there is 5 intersection, then those intersections would be 0 , 1 , 2 , 3 , and 4 right ?

My idea to solve it is using a modified Floyd-Warshall algorithm.

I use edge[k+1][j] += edge[k][k] * edge[k][k][j] rather than
edge[k+1][j] = min ( edge[k][j] , edge[k][k] + edge[k][k][j] ). this is where I made the modification.

After that, I just print the result after checking if a cycle exist for all vertex v that included in the path of u-v.

Sorry about my bad english.

Any help and suggestion would be highly appreciated.

Is there any special or tricky input to consider ?

In all cities, intersections are numbered sequentially from 0 to the ``largest'' intersection

It means that if there is 5 intersection, then those intersections would be 0 , 1 , 2 , 3 , and 4 right ?

My idea to solve it is using a modified Floyd-Warshall algorithm.

I use edge[k+1][j] += edge[k][k] * edge[k][k][j] rather than
edge[k+1][j] = min ( edge[k][j] , edge[k][k] + edge[k][k][j] ). this is where I made the modification.

After that, I just print the result after checking if a cycle exist for all vertex v that included in the path of u-v.

Sorry about my bad english.

Any help and suggestion would be highly appreciated.

I get WA when i submit it but it works correct for any test on my computer(also for multigraphs too)
Can someone help me.
This is my code.
[pascal]program acm125;
var a,b,c,s,sum:array[0..30,0..30] of integer;
number,i,j,n,k,u,v,max:integer;
procedure mult;
var i,j,k:integer;
begin
for i:=0 to n do
for j:=0 to n do
c[i,j]:=0;
for i:=0 to n do
for j:=0 to n do
for k:=0 to n do
begin
c[i,j]:=c[i,j]+b[i,k]*a[k,j];
end;
for i:=0 to n do
for j:=0 to n do
begin
s[i,j]:=s[i,j]+c[i,j];
b[i,j]:=c[i,j];
c[i,j]:=0;
end;
end;
begin
number:=-1;
while not eof do
begin
number:=number+1;
read(n);
for i:=0 to n do
for j:=0 to n do
a[i,j]:=0;
v:=0;
max:=0;
for i:=1 to n do
begin
read(u,v);
if max<u then max:=u;
if max<v then max:=v;
a[u,v]:=a[u,v]+1;
end;
n:=max;
for i:=0 to n do
for j:=0 to n do
begin
b[i,j]:=a[i,j];
s[i,j]:=a[i,j];
end;

for i:=1 to n do
mult;
for i:=0 to n do
for j:=0 to n do
sum[i,j]:=s[i,j];
for i:=1 to n+1 do
mult;
for i:=0 to n do
for j:=0 to n do
if sum[i,j]<>s[i,j] then sum[i,j]:=-1;
writeln('matrix for city ',number);
for i:=0 to n do
begin
for j:=0 to n do
write(sum[i,j],' ');
writeln;
end;
end;
end.[/pascal]

got AC, thanks