提交记录 24pts

代码：

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 3e3+10;
const ll inf = 1e18;
struct edge{
	int v;
	ll w;
	bool operator < (const edge &s) const{
		return s.w < w;
	}
};
vector<edge> g[N];
queue<int> q;
int n,m,vis[N],num[N];
ll dis[N],d[N],ans[N];
bool spfa(int s){
	for(int i = 0;i <= n;i++) d[i] = inf;
	d[s] = 0;
	q.push(s);
	vis[s] = 1;
	while(!q.empty()){
		int u = q.front();
		q.pop();
		vis[u] = 0;
		for(int i = 0;i < g[u].size();i++){
			int v = g[u][i].v;
			ll w = g[u][i].w;
			if(d[v] > d[u] + w){
				d[v] = d[u] + w;
				num[v] = num[u] + 1;
				if(num[v] >= n+1) return false;
				if(vis[v] == 0){
					q.push(v);
					vis[v] = 1;
				}
			}
		} 
	}
	return true;
}
void dijkstra(int s){
	priority_queue<edge> pq;
	memset(vis,0,sizeof(vis));
	for(int i = 1;i <= n;i++) dis[i] = inf;
	dis[s] = 0;
	pq.push({s,0});
	while(!pq.empty()){
		int u = pq.top().v;
		pq.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = 0;i < g[u].size();i++){
			int v = g[u][i].v;
			ll w = g[u][i].w;
			if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				pq.push({v,dis[v]});
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= m;i++){
		int u,v;
		ll w;
		scanf("%d%d%lld",&u,&v,&w);
		g[u].push_back({v,w});
	}
	for(int i = 1;i <= n;i++){
		g[0].push_back({i,0});
	}
	if(!spfa(0)){
		printf("-1");
		return 0;
	}
	for(int i = 1;i <= n;i++){
		for(int j = 0;j < g[i].size();j++){
			g[i][j].w = g[i][j].w + d[i] - d[g[i][j].v];
		}
	}
	for(int i = 1;i <= n;i++){
		dijkstra(i);
		for(int j = 1;j <= n;j++){
			if(dis[j] < inf) ans[i] = ans[i] + j * (dis[j] - d[i] + d[j]);
			else ans[i] = ans[i] + (j * 1000000000);
		} 
	} 
	for(int i = 1;i <= n;i++){
		printf("%lld\n",ans[i]);
	}
	
	return 0;
}

若帮本人调出来，直接关注（无需互关）