https://www.luogu.com.cn/record/128433691

#include<bits/stdc++.h>

using namespace std;

const int N = 10e3+10, M = 1e5 + 10, INF = 0x3f3f3f3f;

int dis[N], vis[N], h[N], to[M], w[M], ne[M], idx;

int n, m;

void add(int u, int v, int c) {
    to[++idx] = v;
    w[idx] = c;
    ne[idx] = h[u];
    h[u] = idx;
}
int dijkstra(int start, int end) {
    memset(dis, INF, sizeof dis);
    memset(vis, 0, sizeof vis);
    
    dis[start] = 0;  //起点距离为0
    for (int i = 1; i <= n; i++) {
    	
        int t = -1;
        
        for (int j = 1; j <= n; j++)//在还未确定最短路的点中，找到距离最小的点
            if (!vis[j] && (t == -1 || dis[j] < dis[t]))
                t = j;
                
        vis[t] = 1;
        
        for (int j = h[t]; j != -1; j = ne[j]) { //用t更新其他点的距离
            int k = to[j];
            dis[k] = min(dis[k], dis[t] + w[j]);
        }
    }
    return dis[end];
}
int main() {
    cin >> n >> m ;
    memset(h, -1, sizeof h); //初始化h数组
    int x, y, z;
    for (int i = 1; i <= m; i++) { //输入边
        cin >> x >> y >> z;
        add(x, y, z);
    }
    
    int ans = 0;
    for (int i=2;i<=n;i++)
    {
    	ans+=dijkstra(1, i);
    	ans+=dijkstra(i, 1);
	}

    

    cout << ans;
    return 0;
}

用spfa做的还有70分呢，用邻接矩阵的40分，这次用链式前向星为何也40分？

球调