LCC '21 Contest 3 S3 - Roundabout

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 4.0s
Java 8 10.0s
Memory limit: 256M

Problem type

Neru has a connected graph with N nodes numbered from 1 to N. The nodes are connected by a network of N bidirectional edges. The graph has no duplicate edges.

He defines a roundabout walk as the shortest traversal from a node to itself, where during the traversal, the same edge cannot be used twice in a row. This means that the move from node b to node a isn't possible if the previous move was from node a to node b.

He asks you to sum up the length of the roundabout walks for every node in the graph and output the answer modulo 10^{9}+7.

Note: In a roundabout walk, he can use the same edge twice, but not twice in a row.

Input Specification

The first line of input contains an integer, N (3 \le N \le 10^{6}).

Each of the next N lines contains three space-separated integers, a_i (1 \le a_i \le N), b_i (1 \le b_i \le N), and c_i (1 \le c_i \le 10^{6}), representing a bidirectional connection between node a_i and node b_i with length c_i. The graph has no duplicate edges and a_i \neq b_i.

Output Specification

Output a single integer, the sum of all roundabout walks, modulo 10^{9}+7.


Subtask 1 [15%]

(3 \le N \le 10^{3})

Subtask 2 [85%]

(3 \le N \le 10^{6})

Sample Input 1

1 2 2
2 3 3
3 1 1
1 4 1

Sample Output 1



The length of the roundabout walks starting from nodes 1, 2, and 3 is 6. The length of the roundabout walk starting from node 4 is 8. Therefore, the sum of the roundabout walks is 6+6+6+8=26.


There are no comments at the moment.