Is there any polynomial time solution?

> 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

> > 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. 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
asked that stupid polynomial question.


> > > 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" : 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".

but how to judge whether there's a cycle?

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

Edited by author 23.07.2008 05:54

I can't understand why if there is cycle, the answer is always yes -> what about this test:


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



Edited by author 21.07.2009 12:43

Because there is a cycle with length 9, and we can ride this path unlimited number of times.

"The race may start and finish anyplace on the road"