ADACYCLE - Ada and Cycle

no tags 

Ada the Ladybug is on a trip in Bugindia. There are many cities and some uni-directional roads connecting them. Ada is wondering about the shortest path, which begins in a city and ends in the same city. Since Ada likes short trips, she asked you to find the length of such path for each city in Bugindia.


The first line will contain 0 < N ≤ 2000, the number of cities.

Then N lines follow, each containing N integers 0 ≤ Hij ≤ 1. One means, that there is a road between i and j (zero means there isn't a road).


Print N lines, the length of shortest path which begins in city i and ends in city i. If the path doesn't exist, print "NO WAY" instead.

Example Input

0 1 1 1 1
1 0 0 0 1
0 0 1 1 0
0 0 1 0 0
0 0 0 1 0

Example Output


Example Input

0 1 0 0 1
0 0 1 0 0
0 0 0 1 0
0 0 0 0 1
1 0 0 0 0

Example Output


hide comments
glydon: 2022-10-15 04:21:28

I was facing TLE in the problem until I realized that when you are getting demanded source as an adjacent of someone,
tackle it then and there because if you put desired source back into the queue and let's suppose it's distance is 9 then all other elements present in the queue with distance 8 will waste time to find the desired source.

cpchef7: 2022-01-24 20:38:41

Got an AC, in first time for first time

rushi2001: 2021-05-20 00:22:48

Simple bfs from every point to find shortest distance to itself .
time complexity (n^2)
so 2000*2000 = 4000000 < 1e8
works fine .

ktkrsk: 2020-06-05 17:13:08

Is it solvable in C#? Im getting TLE with BFS with Adj list and fast IO(StringBuilder etc). Or do I need to use the SCC?

mr_dot_convict: 2019-06-03 10:26:07

The time limit shown is 3s but I found none of the accepted solutions below 3s. A naive bfs solution without any optimizations(except adjacency list if you call it an optimization) works well too but in approx. 5s.
The optimization I went for was to extract out *strongly connected components* as seperate graphs and call bfs upon the new adjacency list created by strongly connected components. This gives AC in 2.3s (which is the fastest I've seen till now in last 5 pages of submissions, please correct me if I'm wrong). @morass Do you have some other optimizations that can improve it further?

Last edit: 2019-06-03 10:37:53
snjumaheshwari: 2019-05-25 16:19:16

Solved but not satisfied. Changed cout (with fast i/o) to printf and worked.
Though i feel complexity is still O(V*(E+V)) and in worst case it can go upto n**3.
(consider a matrix where A[i][j] =1 if i> j ..Having NO CYCLE and upto n**2 edges.)
any hint for better approch .

vjvjain0: 2019-05-20 00:12:13

Got to learn applications of bfs and dfs. Sad that same logic which passed in CPP won't pass in Java :(

dschen: 2019-03-18 16:09:33

why I always got Segmentation Fault ...

I thought I hadn't any invalid access...
and my MAX_N was set as 2200...

Last edit: 2019-03-18 16:17:39
ameyanator: 2018-02-20 17:56:10

To get an AC you need to optimize your code so that you only consider those edges that the current node stems to. You should know this before or preprocess it.

anurag_tangri: 2017-11-09 19:38:05

i am getting TLE please give some hint !

Added by:Morass
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU