题解 | 邮递员送信 （单源正反带权最短路）

本题题意是对于每一个点i，向结果累加1->i与i->1的最短路长度。

我们知道朴素版Dijkstra可以在O(n^2)的复杂度内处理出单个点到全图的单源最短路。最最朴素的思想是对于每一个点，都去求出其到其余所有点的最短路，但是这样时间复杂度来到了O(n^3)。

注意到i->1的最短路等价于1沿着反向边到i的最短路，我们可以分两个邻接表分别存正反边，分别存储u指出的点和指向u的点。最后分别以1为起点和终点做两次朴素版Dijkstra即可。

#include<bits/stdc++.h>
#include <climits>
using namespace std;
#define int long long
const int N=1e3+5;
int n, m, w[N][N], vis[N], s1[N], s2[N];
vector<int> g[N], f[N];
signed main() {
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        int u, v;
        cin>>u>>v>>w[u][v];
        g[u].push_back(v);
        f[v].push_back(u);
    }
    //以1为起点与终点做两次单源带权最短路
    memset(s1, 0x3f, sizeof(s1));
    s1[1]=0;
    for(int tim=1; tim<=n; tim++) {
        int u=n+1;
        for(int i=1; i<=n; i++) {
            if(!vis[i]&&s1[i]<s1[u]) u=i; 
        }
        vis[u]=1;
        for(auto &v: g[u]) {
            s1[v]=min(s1[v], s1[u]+w[u][v]);
        }
    }
    memset(vis, 0, sizeof(vis));
    memset(s2, 0x3f, sizeof(s2));
    s2[1]=0;
    for(int tim=1; tim<=n; tim++) {
        int u=n+1;
        for(int i=1; i<=n; i++) {
            if(!vis[i]&&s2[i]<s2[u]) u=i; 
        }
        vis[u]=1;
        for(auto &v: f[u]) {
            s2[v]=min(s2[v], s2[u]+w[v][u]);
        }
    }
    int ans=0;
    for(int i=2; i<=n; i++) {
        ans+=s1[i]+s2[i];
    }
    cout<<ans;
}
// 愿能安眠于好心情的告别日