The problem with the proposed depth first search is that it can try many very long paths, requiring exponential time, before it ever finds the correct cycle, even if the cycle is very short. A breadth-first search will avoid this, and using dynamic programming principles can accomplish the equivalent of a breadth-first search without excessively large memory requirements.
Use an nxn table H[n][n] to represent the possible states after t moves. H[i][j] is the possible happiness at time t for a person starting at room i and now in room j. Start with the table initialized to min, a very large negative value, and the diagonal set to zero. This indicates that at t=0, you could start in any room with zero happiness. Then increment t and compute the new H, where H[i][j] is the maximum value of H[i][k]+Ckj for all values of k. As soon as you have a positive value in the diagonal, t is the length of the shortest cycle. Don On Jan 5, 7:07 am, saurabh singh <saurab...@gmail.com> wrote: > This problem is taken fromwww.codeforces.com.....Whatcan be the possible > approaches?? > > A smile house is created to raise the mood. It has *n* rooms. Some of the > rooms are connected by doors. For each two rooms (number *i*and *j*), which > are connected by a door, Petya knows their value *c**ij* — the value which > is being added to his mood when he moves from room *i* to room *j*. > > Petya wondered whether he can raise his mood infinitely, moving along some > cycle? And if he can, then what minimum number of rooms he will need to > visit during one period of a cycle? > Input > > The first line contains two positive integers *n* and *m* (), where *n* is > the number of rooms, and *m* is the number of doors in the Smile House. > Then follows the description of the doors: *m* lines each containing four > integers *i*, *j*, *c**ij* и *c**ji* (1 ≤ *i*, *j* ≤ *n*, *i* ≠ *j*, - 104≤ > *c**ij*, *c**ji* ≤ 104). It is guaranteed that no more than one door > connects any two rooms. No door connects the room with itself. > Output > > Print the minimum number of rooms that one needs to visit during one > traverse of the cycle that can raise mood infinitely. If such cycle does > not exist, print number 0. > Sample test(s) > input > > 4 4 > 1 2 -10 3 > > 1 3 1 -10 > 2 4 -10 -1 > 3 4 0 -3 > > output > > 4 > > Note > > Cycle is such a sequence of rooms *a*1, *a*2, ..., *a**k*, that *a*1 is > connected with *a*2, *a*2 is connected with *a*3, ..., *a**k* - 1 is > connected with *a**k*,*a**k* is connected with *a*1. Some elements of the > sequence can coincide, that is, the cycle should not necessarily be simple. > The number of rooms in the cycle is considered as *k*, the sequence's > length. Note that the minimum possible length equals two. > > Saurabh Singh > B.Tech (Computer Science) > MNNIT > blog:geekinessthecoolway.blogspot.com -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
