시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 (추가 시간 없음) | 1024 MB | 27 | 4 | 4 | 80.000% |
Beaverland consists of $N$ cities, numbered from $1$ to $N$. There are $M$ roads connecting cities, numbered from $1$ to $M$. The road $i$ ($1 ≤ i ≤ M$) connects the city $A_i$ and the city $B_i$ bidirectionally, and the length of the road $i$ is $C_i$. It is possible to move from any city to any other city by passing through a number of roads.
Bitaro is a beaver living in the city $1$. He goes to a school in the city $N$. He usually takes the same route to the school. His route to the school satisfies the following conditions.
Since today is a fine day, Bitaro decided to go back to his home by taking a roundabout way. Namely, he will take a route longer than $L$ from the city $N$ to the city $1$. Since Bitaro is easily bored, he does not want to visit the same city more than once. Therefore, when he takes a roundabout way to his home, it is not allowed to visit the same city more than once, and it is not allowed to turn back on the way.
Given information of the cities and the roads in Beaverland, write a program which determines whether there exists a roundabout way from the school to Bitaro’s home.
Read the following data from the standard input. Given values are all integers.
$N$ $M$
$A_1$ $B_1$ $C_1$
$A_2$ $B_2$ $C_2$
$\vdots$
$A_M$ $B_M$ $C_M$
Write one line to the standard output. Output $1$ if there exists a route to Bitaro’s home longer than $L$ without visiting the same city more than once. Otherwise, output $0$.
번호 | 배점 | 제한 |
---|---|---|
1 | 7 | $M ≤ 40$. |
2 | 15 | $N ≤ 18$. |
3 | 23 | $M - N ≤ 13$. |
4 | 35 | For any distinct cities $a$, $b$, $c$, there is a route from the city $a$ to the city $c$ without passing through the city $b$. |
5 | 20 | No additional constraints. |
4 4 1 2 1 1 3 2 2 4 4 3 4 3
0
In this sample input, the minimum distance from the city $1$ (Bitaro’s home) to the city $4$ (school) is $5$. There are two routes to Bitaro’s home without visiting the same city more than once.
Since there does not exist a route to Bitaro’s home longer than $5$ without visiting the same city more than once, output $0$.
This sample input satisfies the constraints of all the subtasks.
4 4 1 2 1 1 3 3 2 4 4 3 4 3
1
In this sample input, the minimum distance from the city $1$ (Bitaro’s home) to the city $4$ (school) is $5$. There are two routes to Bitaro’s home without visiting the same city more than once.
Since there exists a route to Bitaro’s home longer than $5$ without visiting the same city more than once, output $1$.
This sample input satisfies the constraints of all the subtasks.
3 4 1 2 1 1 2 2 1 3 3 1 3 3
0
This sample input satisfies the constraints of Subtasks 1, 2, 3, 5.
4 5 1 2 1 1 3 2 2 4 4 3 4 3 2 3 1
1
This sample input satisfies the constraints of all the subtasks.
12 17 2 4 656247308 4 6 106088453 1 5 754343261 9 12 497827261 3 8 759830309 3 4 61084725 1 6 324702188 3 6 415317430 7 12 846175092 5 8 278621369 1 10 891247646 10 12 755236904 6 8 511967203 5 6 597197970 1 7 800309458 7 9 348347831 10 11 134217757
0
This sample input satisfies the constraints of Subtasks 1, 2, 3, 5.