Обсуждение @ 1227. Чемпионат по ралли @ Timus Online Judge

asif How can this be solved? Can anyone help?(+) [10] // Задача 1227. Чемпионат по ралли 10 ноя 2002 22:15

Is there any polynomial time solution?

WAZZAP I can [9] // Задача 1227. Чемпионат по ралли 14 ноя 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

Ural Re: I can [3] // Задача 1227. Чемпионат по ралли 18 ноя 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
>
>

asif Thanks a lot (+) [1] // Задача 1227. Чемпионат по ралли 22 ноя 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
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
> >
> >

Denis Koshman No subject // Задача 1227. Чемпионат по ралли 23 июл 2008 05:52

Edited by author 23.07.2008 05:54

WAZZAP Multigraph // Задача 1227. Чемпионат по ралли 23 ноя 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".

Fat Peter Re: I can [1] // Задача 1227. Чемпионат по ралли 28 апр 2004 14:46

but how to judge whether there's a cycle?

marius dumitran Re: I can // Задача 1227. Чемпионат по ралли 29 апр 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

Hristian Hristov Re: I can [2] // Задача 1227. Чемпионат по ралли 21 июл 2009 12:42

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

Petr Huggy (Pskov) Why YES? // Задача 1227. Чемпионат по ралли 21 ноя 2010 12:32

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

yyll Re: I can // Задача 1227. Чемпионат по ралли 8 окт 2020 20:56

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

Обсуждение задачи 1227. Чемпионат по ралли