求助 CE

#include <bits/stdc++.h>

#define endl '\n'

#define int long long

const int N = 3e3 + 5;

struct Edge{
  int x, y, c;
}e[( N << 1 ) + N];

struct Node{
  int x, c;
  bool operator<(const Node &i) const {
    return c > i.c;
  }
};

int n, m, dis[N][N];
bool v[N];

vector<Node>g[N];

bool Bellman_Ford(int s){
  bool flag = 0;
  dis[s][s] = 0;
  for(int i = 1; i <= n; ++i){
    for(int j = 1; j <= m; ++j){
      if(dis[s][e[j].x] != LLONG_MAX >> 1 && dis[s][e[j].x] + e[j].c < dis[s][e[j].y]){
        dis[s][e[j].y] = dis[s][e[j].x] + e[j].c;
        flag = 1;
      }
    }
  }
  return flag;
}

void Dijkstra(int s){
  priority_queue<Node>que;
  dis[s][s] = 0;
  que.push({s, 0});
  while(!que.empty()){
    Node u = que.top();
    que.pop();
    if(v[u.x] == 1) continue;
    v[u.x] = 1;
    for(auto to : g[u.x]){
      if(dis[s][u.x] + to.c < dis[s][to.x]){
        dis[s][to.x] = dis[s][u.x] + to.c;
        que.push({to.x, dis[s][to.x]});
      }
    }
  }
}

void Johnson(){
  for(int i = 1; i <= n; ++i){
    fill(v + 1, v + n + 1, 0);
    Dijkstra(i);
  }
}

signed main(){
  cin >> n >> m;
  fill(dis[0] + 0, dis[n] + n + 1, LLONG_MAX >> 1);
  for(int i = 1; i <= m; ++i)
    cin >> e[i].x >> e[i].y >> e[i].c;
  for(int i = 1; i <= n; ++i) e[++m] = {0, i, 0};
  Bellman_Ford(0);
  for(int i = 1; i <= m; ++i) 
    e[i].c = dis[0][e[i].x] - dis[0][e[i].y] + e[i].c;
  for(int i = 1; i <= m; ++i) 
    g[e[i].x].push_back({e[i].y, e[i].c});
  Johnson();
  for(int i = 1; i <= n; ++i){
    int ans = 0;
    for(int j = 1; j <= n; ++j)
      ans += dis[i][j] * j;
    cout << ans << endl;
  }
  return 0;
}