[daily question in summer] letter delivery by p1629 postman in Luogu (to be continued...)

Topic link ：P1629 The postman delivers the mail - Luogu | New ecology of computer science education (luogu.com.cn)

Title Description

There's a postman to deliver , The post office is at the node 1. All in all, he will send n-1  things , The destinations are nodes 2  To the node n. Because of the heavy traffic in this city , So all roads are one-way , share m  road . This postman can only carry one thing at a time , also After delivering each item, you must return to the post office . Please finish the delivery n-1  Something and Finally back to the post office The least time required .

Input format

The first line contains two integers ,n  and m, Indicates the number of nodes and roads in the city .

Line two to line two (m+1)  That's ok , Three integers per row ,u,v,w, From u  To v  There is a passage time of w  The path of .

Output format

Output only one line , Contains an integer , For the least time needed .

Examples #1

The sample input #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

Sample output #1

83

Tips

about 30%  The data of ,1<= n <= 200.

about 100%  The data of ,1<= n <= 10^3,1 <= m <= 10^5,1<= u,v <= n,1 <= w <= 10^4, Input ensures that any two points can reach each other .

AC code:（ Need to read fast +O2 Optimize ）

#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; //  Initialize that the distance between vertices is positive infinite  
	
	while(m--)
	{
		ll u,v,w;
		cin>>u>>v>>w;
		e[u][v]=min(e[u][v],w); //  There may be duplicate edges , Save minimum weight .
	}
	
	// Floyd  Algorithm core statement 
	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;
}