#P1629. P1629 邮递员送信
P1629 邮递员送信
P1629 邮递员送信
普及/提高- | 来源:洛谷 | 原题链接
题意
邮递员从 号城市出发,要给 每个城市送信,送完回到 号(道路是有向的)。他必须为每个城市单独跑一趟(送完即回)。求最少总时间,即 $\sum_{i=2}^{n}\big[\text{dist}(1,i)+\text{dist}(i,1)\big]$。
输入格式
第一行包括两个整数, 和 ,表示城市的节点数量和道路数量。
第二行到第 行,每行三个整数,,表示从 到 有一条通过时间为 的道路。
输出格式
输出仅一行,包含一个整数,为最少需要的时间。
输入输出样例
样例 1 输入
5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2
样例 1 输出
83
数据范围
,,;输入保证任意两点都能互相到达。
提示
考点:正反图各跑一遍 Dijkstra。易错点:① 的距离不能靠「无向图」偷懒——图是有向的,必须建反图后求 ;② 个目的地都算,别漏 。