9583 - 最小树形图
时间限制 : 1 秒
内存限制 : 256 MB
给定包含 n 个结点, m 条有向边的一个图。试求一棵以结点 r 为根的最小树形图,并输出最小树形图每条边的权值之和,如果没有以 r 为根的最小树形图,输出 -1。
输入
第一行包含三个整数 n,m,r,意义同题目所述。
接下来 m 行,每行包含三个整数 u,v,w,表示图中存在一条从 u 指向 v 的权值为 w 的有向边。
输出
如果原图中存在以 r 为根的最小树形图,就输出最小树形图每条边的权值之和,否则输出 -1。
样例
输入
4 6 1 1 2 3 1 3 1 4 1 2 4 2 2 3 2 1 3 4 1
输出
3
输入
4 6 3 1 2 3 1 3 1 4 1 2 4 2 2 3 2 1 3 4 1
输出
4
输入
4 6 2 1 2 3 1 3 1 4 1 2 4 2 2 3 2 1 3 4 1
输出
-1
提示
样例 1 解释
最小树形图中包含第 2, 5, 6 三条边,总权值为 1 + 1 + 1 = 3
样例 2 解释
最小树形图中包含第 3, 5, 6 三条边,总权值为 2 + 1 + 1 = 4
样例 3 解释
无法构成最小树形图,故输出 -1 。
数据范围
对于所有数据,1 \leq u, v \leq n \leq 100, 1 \leq m \leq 10^4, 1 \leq w \leq 10^6。