求助全源最短路

#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

const int MAXN = 3e3 + 5;
int n, m, u, v, w, h[MAXN], cnt[MAXN], dist[MAXN];
vector<pii> graph[MAXN];
bool visited[MAXN];

bool SPFA(){
    fill(h, h + MAXN, 1e9);
    queue<int> q;
    q.push(0);
    h[0] = 0, cnt[0] = 1;
    while(!q.empty()){
        auto nownode = q.front();
        q.pop();
        if(cnt[nownode] > n) return false;
        for(auto i : graph[nownode]){
            int e = i.first, w = i.second;
            if(h[e] > h[nownode] + w){
                h[e] = h[nownode] + w;
                q.push(e);
                cnt[e] ++;
            }
        }
    }
    return true;
}

void dijkstra(int st){
    fill(dist, dist + MAXN, 1e9);
    memset(visited, 0, sizeof(visited));
    dist[st] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> pq;
    pq.push({0, st});
    while(!pq.empty()){
        auto nownode = pq.top();
        pq.pop();
        if(visited[nownode.second]) continue;
        visited[nownode.second] = true;
        for(auto nextnode : graph[nownode.second]){
            if(visited[nextnode.first]) continue;
            if(dist[nownode.second] + nextnode.second < dist[nextnode.first]){
                dist[nextnode.first] = dist[nownode.second] + nextnode.second;
                pq.push({dist[nextnode.first], nextnode.first});
            }
        }
    }
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= m; i ++){
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
    }
    for(int i = 1; i <= n; i ++) graph[0].push_back({i, 0});
    if(SPFA() == false){
        cout << -1 << endl;
        return 0;
    }
    for(int i = 1; i <= n; i ++){
        for(auto node : graph[i]){
            node.second = node.second + h[i] - h[node.first];
        }
    }
    for(int i = 1; i <= n; i ++){
        dijkstra(i);
        int sum = 0;
        for(int j = 1; j <= n; j ++){
            sum += j * dist[j];
        }
        cout << sum << endl;
        // for(int j = 1; j <= n; j ++){
        //     cout << dist[j] << " ";
        // }
        // cout << endl;
    }
    // for(int i = 1; i <= n; i ++) cout << h[i] << " ";
    // cout << endl;
    return 0;
}