题解 | 邮递员送信

#include<bits/stdc++.h>
#include <cstring>

using namespace std;
#define int long long
#define x first
#define y second
#define space ' '
#define endl '\n'
#define pb push_back
#define all(x) x.begin(),x.end()

#define debug(x) x<<' '
typedef pair<int, int> PII;

const int N = 1e3 + 10;
const int INF = 0x3f3f3f3f3f3f3f3fLL;
const int inf = 0x3f3f3f3f3f3f3f3fLL;
const int mod = 1e9 + 7;
const int MOD = 998244353;

int n, m, k, q;
int g[N][N],dist[N],dist1[N];//反向建图
bool st[N],st1[N];
void solve() {
memset(dist,0x3f,sizeof(dist));
//cout<<dist[2];
dist[1]=0;
for(int i=0;i<n-1;i++){
int t=-1;
for(int j=1;j<=n;j++){
    if(!st[j]&&(t==-1||dist[t]>dist[j])){
        t=j;
    }
}
for(int j=1;j<=n;j++){
  //  cout<<"-------";
    dist[j]=min(dist[j],dist[t]+g[t][j]);
}
st[t]=true;
//cout<<dist[t]<<endl;
}
}
void solve1() {
memset(dist1,0x3f,sizeof(dist1));
//cout<<dist[2];
dist1[1]=0;
for(int i=0;i<n-1;i++){
int t=-1;
for(int j=1;j<=n;j++){
    if(!st1[j]&&(t==-1||dist1[t]>dist1[j])){
        t=j;
    }
}
for(int j=1;j<=n;j++){
  //  cout<<"-------";
    dist1[j]=min(dist1[j],dist1[t]+g[j][t]);
}
st1[t]=true;
//cout<<dist[t]<<endl;
}

}

signed main() {
    // double start=(double)clock()/CLOCKS_PER_SEC;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout << fixed << setprecision(3);
    int t = 1;
cin>>n>>m;
int w;
memset(g,0x3f,sizeof(g));//将点之间的距离的每一个值设置成很大的数
while(m--){
   cin>>k>>q>>w;
   g[k][q]=min(g[k][q],w);
   
}
    // cin>>t;
    while (t--) {
        solve();
        solve1();
    }

   int ans=0;
   for(int i=1;i<=n;i++){
    ans+=dist[i];
    ans+=dist1[i];
   }

  cout<<ans;

    return 0;
}