#Y. 「一本通 3.2 练习 4」新年好

Type: Default

1000ms

512MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

原题来自：CQOI 2005

重庆城里有 $n$ 个车站， $m$ 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。

佳佳的家在车站 $1$ ，他有五个亲戚，分别住在车站 $a,b,c,d,e$ 。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？

第一行： $n,m$ 为车站数目和公路的数目。

第二行： $a,b,c,d,e$ 为五个亲戚所在车站编号。

以下 $m$ 行，每行三个整数 $x,y,t$ ，为公路连接的两个车站编号和时间。

输出仅一行，包含一个整数 $T$ ，为最少的总时间。

对于全部数据，$1\le n \le 50000,1\le m \le 10^5,1\lt a,b,c,d,e\le n,1 \le x,y \le n,1 \le t \le 100$。