KOICOST - Cost
You are given an undirected graph with N vertices and M edges, where the weights are unique.
There is a function Cost(u, v), which is defined as follows:
While there is a path between vertex u and v, delete the edge with the smallest weight. Cost(u,v) is the sum of the weights of the edges that were deleted in this process.
For example, from the graph above (same as the sample input), Cost(2,6) is 2+3+4+5+6 = 20.
Given an undirected graph, your task is to calculate the sum of Cost(u,v) for all vertices u and v, where u < v. Since the answer can get large, output the answer modulo 10^9.
Input
The first line of the input consists of two integers, N and M. (1 <= N <= 100,000, 0 <= M <= 100,000)
The next M lines consists of three integers, u, v, and w. This means that there is an edge between vertex u and v with weight w. (1 <= u, v <= N, 1 <= w <= 100,000)
Output
Output the sum specified in the problem statement.
Example
Input: 6 7
1 2 10
2 3 2
4 3 5
6 3 15
3 5 4
4 5 3
2 6 6 Output: 256
hide comments
supergaber:
2024-04-16 15:36:39
Good problem Last edit: 2024-04-16 15:37:17 |
|
abhi_8:
2023-07-27 11:05:50
Remember that it is 10^9 and not 10^9 + 7 for modulus |
|
ivanmilinovic:
2023-06-30 11:31:10
Good task. Last edit: 2023-07-01 10:00:39 |
|
ankhang277:
2021-08-03 15:27:24
Wr in someway that i strongly believe my code was right |
|
jeaf_dean:
2021-06-05 15:57:30
"While there is a path between vertex u and v, delete the edge with the smallest weight" doesn't imply weight in a given path.
|
|
greenindia:
2021-03-06 18:19:25
i think its the best question on dsu |
|
lamda_cdm_10:
2021-02-26 17:07:10
Beautiful problem on DSU . Enjoy solving it !!
|
|
iamfarraz:
2020-11-02 22:18:06
why sigabrt : ((( |
|
anish1712:
2020-06-28 22:59:07
I removed SIGSEGV by adding
|
|
luvkumbi:
2020-03-13 09:28:52
getting SIGSEGV ....any help?.....perfectly runs on my ide |
Added by: | Lawl |
Date: | 2011-06-01 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | 2011 KOI Regional |