Is there any polynomial time solution?

I passed all test cases mentioned in the discussion.

There are 4 tests in my algorithm:
- is there a loop (from M and N) ?
- is the graph connected ?
- is there a cycle?
- for each component of the graph:
  find the longest path and compare the length with S

any hint?

Edited by author 06.09.2017 11:02

Edited by author 06.09.2017 11:02

Graph can have loops and multiple edges.

Edited by author 28.10.2019 20:10

An example from other discussions:

input:
4 3 12
1 2 5
1 3 4
3 4 4

output:
YES

displays the correct answer.
Tell me more examples, please.

In the algorithm, I check loops, two-way roads, cycles, and then look for a way longer than necessary.

UPD: WA#18

Edited by author 20.03.2019 19:17

Can you suggest an example for this test?

you can use to check "YES" that simple DSU algorithm.
because DSU algorithm gives us all cycle, knot, multigraph ... so on

try this test

input:
4 3 12
1 2 5
1 3 4
3 4 4

output:
YES

Can you give me some tests. I check if it is multigraph and if there are cycles. After that I get the longest path and if it is lower than S I ouput NO. But still WA :(

What is the output?

1 1 3
1 1 2

Rather simple tests…
For this test my AC program gives “NO”:
4 2 13
1 2 15
3 4 10
But the correct answer is YES.
So as I understood, in all your tests, if graph is unconnected and there is no cycle in it, then the max length of path always contain the last (m) vertex…
So all programs which use this algorithm passed all your tests:
First, check knots, multigraph;
Second, for (I, 1, n) - check is the i vertex is in the circle;
Third, find the max length of path of that tree, which contain the last vertex; and compare it with s.
INSTEAD: Third, find the max length of paths ALL TREES, and all of them compare with s.

Sorry for my English.