ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1227. Rally Championship

How can this be solved? Can anyone help?(+)
Posted by asif 10 Nov 2002 22:15
Is there any polynomial time solution?
I can
Posted by WAZZAP 14 Nov 2002 16:52
> Is there any polynomial time solution?
yes.

- if there is a cycle the answer is always "yes"
- if there is a knot (ex. 2 2 edges), the answer is also "yes"
- if graph is multigraph, yes too

if all above is false just find the longest path in a tree and
play with it's value in comparsion with route length
Re: I can
Posted by Ural 18 Nov 2002 10:59
> > Is there any polynomial time solution?
> yes.
>
> - if there is a cycle the answer is always "yes"
> - if there is a knot (ex. 2 2 edges), the answer is also "yes"
> - if graph is multigraph, yes too
"multigraph" : what is it? I got WA so many times,any trick?
>
> if all above is false just find the longest path in a tree and
> play with it's value in comparsion with route length
>
>
Thanks a lot (+)
Posted by asif 22 Nov 2002 13:43
Thanks. I did not read the question well enough and thought that the
race must start and end on vertices. How stupid of me! That is why I

> > > Is there any polynomial time solution?
> > yes.
> >
> > - if there is a cycle the answer is always "yes"
> > - if there is a knot (ex. 2 2 edges), the answer is also "yes"
> > - if graph is multigraph, yes too
>       "multigraph" : what is it? I got WA so many times,any trick?
> >
> > if all above is false just find the longest path in a tree and
> > play with it's value in comparsion with route length
> >
> >
Multigraph
Posted by WAZZAP 23 Nov 2002 17:03
>       "multigraph" : what is it? I got WA so many times,any trick?

multigraph can have more than one edge connecting 2 vertices. Those
edges can have different length. So, if there are two or more edges,
connecting 2 vertices, this is just another cycle.

This task is quite tricky and not well-right from the point of
diskrete maths. For example, non-oriented graph can not have knots
(by the difinition), but in this problem this is one of the "triks".
Re: I can
Posted by Failed Peter 28 Apr 2004 14:46
but how to judge whether there's a cycle?
Re: I can
Posted by marius dumitran 29 Apr 2004 02:45
do DFs and if there a return edge than u have a circle
or do n Dijkstra's and if u can get back to the point than u have a circle
No subject
Posted by Denis Koshman 23 Jul 2008 05:52

Edited by author 23.07.2008 05:54
Re: I can
Posted by h1ci 21 Jul 2009 12:42

3 3 1000
1 2 3
2 3 3
1 3 3

Edited by author 21.07.2009 12:43
Why YES?
Posted by Petr Huggy (Pskov) 21 Nov 2010 12:32
Because there is a cycle with length 9, and we can ride this path unlimited number of times.
Re: I can
Posted by yyll 8 Oct 2020 20:56
"The race may start and finish anyplace on the road"