【暑期每日一题】洛谷 P1629 邮递员送信（未完待续...）

题目链接：P1629 邮递员送信 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述

有一个邮递员要送东西，邮局在节点 1。他总共要送 n-1 样东西，其目的地分别是节点 2 到节点 n。由于这个城市的交通比较繁忙，因此所有的道路都是单行的，共有 m 条道路。这个邮递员每次只能带一样东西，并且运送每件物品过后必须返回邮局。求送完这 n-1 样东西并且最终回到邮局最少需要的时间。

输入格式

第一行包括两个整数，n 和 m，表示城市的节点数量和道路数量。

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

输出格式

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

样例 #1

样例输入 #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

提示

对于 30% 的数据，1<= n <= 200。

对于 100% 的数据，1<= n <= 10^3，1 <= m <= 10^5，1<= u,v <= n，1 <= w <= 10^4，输入保证任意两点都能互相到达。

AC code:（需要快读+O2优化）

#include<iostream>

using namespace std;

typedef long long ll;
const int N = 1e3 + 10;
ll e[N][N];
const int INF = 1e8 - 1;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    
	ll n,m;
	cin>>n>>m;
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=n;j++)
			e[i][j] = INF; // 初始化各顶点之间距离均为正无穷 
	
	while(m--)
	{
		ll u,v,w;
		cin>>u>>v>>w;
		e[u][v]=min(e[u][v],w); // 可能会有重复边，保存最小权值。
	}
	
	// Floyd 算法核心语句
	for(ll k=1;k<=n;k++)
		for(ll i=1;i<=n;i++)
			for(ll j=1;j<=n;j++)
				if(e[i][k]+e[k][j]<e[i][j] && e[i][k]<INF && e[k][j]<INF)
					e[i][j]=e[i][k]+e[k][j];
	
	ll time = 0;
	for(ll j=2;j<=n;j++)
		time=time+e[1][j]+e[j][1];
	cout<<time<<endl;

	return 0;
}