#140. 最小树形图

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Epicurus_

题目描述

这是一道模板题。

给定包含 n 个结点, m 条有向边的一个图。试求一棵以结点 r 为根的最小树形图,并输出最小树形图每条边的权值之和,如果没有以 r 为根的最小树形图,输出 -1

输入格式

第一行包含三个整数 n,m,r ,意义同题目所述。

接下来 m 行,每行包含三个整数 u,v,w ,表示图中存在一条从 u 指向 v 的权值为 w 的有向边。

输出格式

如果原图中存在以 r 为根的最小树形图,就输出最小树形图每条边的权值之和,否则输出 -1

样例

样例输入1

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

样例输出 1

3

样例解释 1

最小树形图中包含第 2 5 6 三条边,总权值为 1 + 1 + 1 = 3

样例输入 2

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

样例输出 2

4

样例输出 2

最小树形图中包含第 3 5 6 三条边,总权值为 2 + 1 + 1 = 4

样例输入 3

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

样例输出 3

-1

样例解释 3

无法构成最小树形图,故输出 -1

数据范围与提示

对于所有数据, 1 \leq u, v \leq n \leq 100, 1 \leq m \leq 10^4, 1 \leq w \leq 10^6