送苹果(Apple Delivery S)

题目描述

Bessie 有两只鲜红的苹果要送给她在牛群中的两个朋友。当然，她要走 $C$ 条牛道（$1 \le C \le 2\times 10^5$），这些牛道构成了一个常见的图，方便地连接了 $P$ 个牧场（$1 \le P \le 10^5$），这些牧场的编号从 $1$ 到 $P$：没有牛道从一个牧场通向自身，牛道是双向的，每条牛道都有一个相关的距离，最重要的是，总是可以从任何一个牧场到达另一个牧场。每条牛道连接两个不同的牧场 $P1_i$（$1 \le P1_i \le P$）和 $P2_i$（$1 \le P2_i \le P$），它们之间的距离为 $D_i$。所有距离 $D_i$ 的总和不超过 $2\times 10^9$。

Bessie 要从牧场 $PB$（$1 \le PB \le P$）出发，按任意顺序访问牧场 $PA_1$（$1 \le PA_1 \le P$）和 $PA_2$（$1 \le PA_2 \le P$），送完两个苹果后，求她必须行走的最小总距离。当然，这三个牧场是不同的。

考虑这个用括号标注牧场编号和牛道距离的地图：

               3        2       2
           [1]-----[2]------[3]-----[4]
             \     / \              /
             7\   /4  \3           /2
               \ /     \          /
               [5]-----[6]------[7]
                    1       2

如果 Bessie 从牧场 $[5]$ 出发，将苹果送到牧场 $[1]$ 和 $[4]$，她的最佳路径是：

$5$ -> $6$ -> $7$ -> $4*$ -> $3$ -> $2$ -> $1*$

总距离为 $12$。

输入格式

* 第 $1$ 行：包含五个用空格分隔的整数：$C, P, PB, PA_1$ 和 $PA_2$。

* 第 $2$ 行到第 $C+1$ 行：第 $i+1$ 行描述牛道 $i$，给出它连接的两个牧场及其之间的距离：$P1_i$, $P2_i$, $D_i$。

输出格式

* 第 $1$ 行：Bessie 必须行走的最短距离。

样例输入 #1

9 7 5 1 4
5 1 7
6 7 2
4 7 2
5 6 1
5 2 4
4 3 2
1 2 3
3 2 2
2 6 3

样例输出 #1

12

数据范围

（由 ChatGPT 4o 翻译）

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1300。

测试点分布

出处：原题链接