← 返回题目列表

AtCoder · awc0014_d

D. 往返送货

中文机器翻译题面 查看原题

分数: 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