题解 | 邮递员送信 利用Floyd求最短路

#include<bits/stdc++.h>
using namespace std;
#define int long long

int d[2000][2000];
signed main()
{
	cin.tie(0);cout.tie(0);
	ios::sync_with_stdio(false);//换行用”\n“
	int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==j) d[i][j]=0;
            else d[i][j]=1e9;
        }
    }
    while(m--)
    {
        int u,v,w;
        cin>>u>>v>>w;
        d[u][v]=w;   
    }
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    int ans=0;
    for(int i=2;i<=n;i++)
    {
        ans+=d[1][i];
        ans+=d[i][1];
    }
    cout<<ans;
	return 0;
}