P1629 postman delivering letter

Title Description

There's a postman to deliver , The post office is at the node  11. All in all, he will send  n-1n−1  things , The destinations are nodes  22  To the node  nn. Because of the heavy traffic in this city , So all roads are one-way , share  mm  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-1n−1  Something and Finally back to the post office The least time required .

Input format

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

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

Output format

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

I/o sample

Input #1 Copy

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

Output #1 Copy

83

explain / Tips

about  30\%30%  The data of ,1 \leq n \leq 2001≤n≤200.

about  100\%100%  The data of ,1 \leq n \leq 10^31≤n≤103,1 \leq m \leq 10^51≤m≤105,1\leq u,v \leq n1≤u,v≤n,1 \leq w \leq 10^41≤w≤104, Input ensures that any two points can reach each other .

 // This question needs to get the shortest weight between every two points , So want to use floyd
// open o2 To live through , Otherwise t（ What principle is this , Fantastic! ）

Because the input data , The distance between two points may be more than one , To avoid overwriting , must do Go to the heavy side , Select the minimum distance among multiple inputs as the initial distance between the two points

Because every time the postman delivers a letter, he has to return to the post office （ Starting point ）, Again because floyd Calculate the shortest path between every two points , So the final calculation result is directly in for In circulation ans+=v[1][i]+v[i][1]; that will do

ac Code （ Must open O2 Optimize ）

#include<bits/stdc++.h>
using namespace std;
#define inf 999999
int n,m,v[1010][1010];
int x,y,z;
int main()
{
    memset(v,inf,sizeof(v));
    scanf("%d%d",&n,&m);
    for(int i=1; i<=m; ++i)
    {
        scanf("%d%d%d",&x,&y,&z);
        v[x][y]=min(z,v[x][y]);// Go to the heavy side 
    }
    //flody
    for(int k=1; k<=n; ++k)
        for(int i=1; i<=n; ++i)
            for(int j=1; j<=n; ++j)
                v[i][j]=min(v[i][k]+v[k][j],v[i][j]);
    int ans=0;
    for(int i=2; i<=n; ++i)
        ans+=v[1][i]+v[i][1];// Time of each visit + Time to come back 
    cout<<ans;
    return 0;
}