#P1629. P1629 邮递员送信

P1629 邮递员送信

P1629 邮递员送信

普及/提高- | 来源:洛谷 | 原题链接

题意

邮递员从 11 号城市出发,要给 2∼n2\sim n 每个城市送信,送完回到 11 号(道路是有向的)。他必须为每个城市单独跑一趟(送完即回)。求最少总时间,即 $\sum_{i=2}^{n}\big[\text{dist}(1,i)+\text{dist}(i,1)\big]$。

输入格式

第一行包括两个整数,nn 和 mm,表示城市的节点数量和道路数量。

第二行到第 (m+1)(m+1) 行,每行三个整数,u,v,wu,v,w,表示从 uu 到 vv 有一条通过时间为 ww 的道路。

输出格式

输出仅一行,包含一个整数,为最少需要的时间。

输入输出样例

样例 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

数据范围

1≤n≤1031\le n\le 10^3,1≤m≤1051\le m\le 10^5,1≤w≤1041\le w\le 10^4;输入保证任意两点都能互相到达。

提示

考点:正反图各跑一遍 Dijkstra。易错点:① i→1i\to 1 的距离不能靠「无向图」偷懒——图是有向的,必须建反图后求 1→i1\to i;② n−1n-1 个目的地都算,别漏 i=ni=n。

三、建模套路(计数)

蜀ICP备2025119001号-1