提交记录

代码：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 3005
struct edge{
	int to,da;
};
vector<edge>g[MAXN];
int n,m;
int h[MAXN],cnt[MAXN];
bool vis[MAXN];
inline bool SPFA(){
	queue<int>q;
	for(int i=1;i<=n;i++)
		h[i]=1e9;
	h[0]=0,vis[0]=1;
	q.push(0);
	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].to,w=g[u][i].da;
			if(h[u]+w<h[v]){
				h[v]=h[u]+w;
    				cnt[v]=cnt[u]+1;
    				if(cnt[v]>n)return 1;				
				if(!vis[v]){
				    q.push(v),vis[v]=1;

				}
			}
		}
	}
	return 0;
}
struct node{
	int a,b;
	inline bool operator<(const node &x)const{
		return a>x.a;
	}
};
struct HEAP{
	vector<node>v;
	inline void push(node x){
		v.push_back(x),push_heap(v.begin(),v.end());
	}
	inline void pop(){
		pop_heap(v.begin(),v.end()),v.pop_back();
	}
	inline node top(){
		return v[0];
	}
	inline bool empty(){
		return v.empty();
	}
	inline int size(){
		return v.size();
	}
}q;
int d[MAXN];
bool f[MAXN];
inline void dij(int x){
	int u,v,w;
	for(int i=1;i<=n;i++)
		d[i]=1e9,f[i]=0;
	d[x]=0;
	q.push(node{0,x});
	while(!q.empty()){
		u=q.top().b,q.pop();
		if(!f[u]){
			f[u]=1;
			for(int i=0;i<g[u].size();++i){
				v=g[u][i].to,w=g[u][i].da;
				if(d[u]+w<d[v]){
					d[v]=d[u]+w;
					if(!f[v])q.push(node{d[v],v});
				}
			}
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u].push_back({v,w});
	}
	for(int i=1;i<=n;i++)
		g[0].push_back({i,0});
	if(SPFA())printf("-1");
	else{
		for(int i=1;i<=n;i++)
			for(int j=0;j<g[i].size();j++)
				g[i][j].da+=h[i]-h[g[i][j].to];
		for(int i=1;i<=n;i++){
			long long ans(0);
			dij(i);
			for(int j=1;j<=n;j++)
				if(d[j]==1e9)ans+=j*1e9;
				else ans+=j*(d[j]+h[j]-h[i]);
			printf("%lld\n",ans);
		}
	}
	return 0;
}