分数: 400 分
问题陈述
高桥在一家快递公司兼职。有 N 该区域的配送中心,编号为 1 to N.
有 M 该地区的道路,以及 i第条路连接枢纽 A_i 和集线器 B_i 双向。沿着这条路行驶需要 C_i 双向分钟。
今天,高桥必须离开枢纽 1,总部所在地,将包裹递送给枢纽客户 T,然后返回集线器 1.
具体来说,高桥从枢纽开始 1,按顺序沿道路行驶,访问枢纽 T 旅途中至少一次,并最终返回枢纽 1。他沿途可能会经过其他枢纽,并且允许他多次穿越同一条道路或访问同一枢纽。如果多次经过同一条道路,则每次经过该道路的行驶时间都会相加。
求从高桥出发枢纽时刻起经过的道路的最短可能总行程时间 1 直到他返回中心 1.
如果不存在有效航线(从枢纽站出发的航线) 1,访问中心 T 至少一次,然后返回集线器 1),输出 -1.
约束
- 2 \leq N \leq 10^5
- 1 \leq M \leq 2 \times 10^5
- 2 \leq T \leq N
- 1 \leq A_i < B_i \leq N (特别是没有自循环)
- 1 \leq C_i \leq 10^9
- 至多有一条道路连接任意一对枢纽
- 所有输入值均为整数
输入
N M T A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_M B_M C_M
- 第一行包含集线器数量 N, 道路数量 M,以及集线器编号 必须访问的 T ,以空格分隔。
- 的 i- 以下各项 M 行包含两个集线器的编号 A_i, B_i 由 i第条路,以及时间 C_i 需要沿着那条路行驶,中间用空格隔开。
输出
一行输出高桥出发枢纽的最短总时间 1,访问中心 T 至少一次,然后返回集线器 1。如果不存在有效路由,则输出 -1.
示例输入 1
4 4 3 1 2 5 2 3 3 3 4 2 1 4 10
示例输出 1
16
示例输入 2
5 3 5 1 2 100 3 4 50 4 5 30
示例输出 2
-1
示例输入 3
6 8 4 1 2 10 1 3 15 2 3 5 2 4 20 3 4 8 3 5 12 4 6 6 5 6 3
示例输出 3
46