NOI '20 P6 - Road

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 6.0s
Memory limit: 1G

Problem type

This problem has three extra sample files you can refer to, each of which can be found here.

There are n cities in a country connected by m bidirectional roads. The cities are numbered 1, 2, \dots, n and the roads are numbered 1, 2, \dots, m. Road i connects city u_i and city v_i, and its length is w_i meters. Starting from any city, you may reach any other city via the roads.

The roads are built in a special way. Formally, a simple cycle passing through l roads (here, a simple cycle means a cycle such that no cities are visited twice except the start) may be represented as c_1 \to c_2 \to \dots \to c_{l-1} \to c_l such that for all 1 \le i < l, city c_i and city c_{i+1} are connected directly by a road, city c_1 and city c_l are connected directly by a road, and for all 1 \le i < j \le l, we have c_i \ne c_j. If l > 3, then the roads satisfy the following additional constraint: there exist two non-adjacent cities on the cycle such that the two cities are directly connected by a road, or in other words, there exists 1 \le u < v \le l such that v-u \ge 2, u,v are not 1 and l simultaneously, and city c_u and city c_v are directly connected by a road.

Now the country is going to find a route to renovate between city s and city t. Since the road will be inaccessible during renovation, the country wants to make sure it is possible to reach all other cities starting from any city in the country via the remaining roads during renovation (i.e. roads that are not included in the route to be renovated).

Please find a possible route to renovate and make sure the length is as short as possible.

Input Specification

The first line contains two integers n,m denoting the number of cities and the number of roads. The following m lines contain three integers u_i,v_i,w_i each denoting the endpoints of the roads and the lengths. It is guaranteed that each road connects two different cities, or in other words, u_i \ne v_i. The last line contains two integers s,t denoting the endpoints of the route to be renovated.

Output Specification

The output contains only one integer denoting the minimum possible length of the route to be renovated satisfying the constraints specified in the problem. If there are no feasible solutions, output -1.

Sample Input 1

4 5
1 2 1
2 3 1
3 4 1
1 3 5
2 4 6
1 4

Sample Output 1


The route to be renovated is 1 \to 3 \to 4.

Sample Input 2

2 1
1 2 1
1 2

Sample Output 2


For all test cases, 2 \le n \le 5 \times 10^5, 2 \le m \le 10^6, s \ne t, 1 \le u_i,v_i \le n, u_i \ne v_i, 1 \le w_i \le 10^9.
It is guaranteed for any two roads their endpoints are not entirely the same.
It is guaranteed the roads satisfy the conditions specified in the problem.

Test Case n \le m \le Additional Constraints
1~6 2000 4000 None.
7~10 5 \times 10^5 10^6 The roads have equal lengths.
11~15 All roads satisfying w_i = 1 form a path from s to t,
and the endpoints of the roads with w_i \ne 1 have distance 2 on the path.
16~20 None.


There are no comments at the moment.