提交记录

题目link

#include<bits/stdc++.h>
#define FL(i,a,b) for(int i=(a);i<=(b);i++)
#define FR(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int MAXN = 3e3 + 10;
const int MAXM = 6e3 + 10;
int n, m, cnt, head[MAXN], dis[MAXN], d[MAXN], num[MAXN];
bool vis[MAXN];

struct edge{
	int v,w,nxt;
}e[MAXM<<1];

queue<int> q;

void add (int u,int v,int w){
	e[++cnt].v=v;
	e[cnt].w=w;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}

bool spfa (int x){
	dis[x]=0;
	q.push(x);
	vis[x]=1;
	num[x]++;
	while(!q.empty()){
		int u=q.front();
		q.pop();
		vis[u]=1;
		for(int i=head[u];i;i=e[i].nxt){
			if (dis[e[i].v]>dis[u]+e[i].w){
				dis[e[i].v]=dis[u]+e[i].w;
				if(!vis[e[i].v]){
					q.push(e[i].v);
					vis[e[i].v]=1;
					num[e[i].v]++;
					if(num[e[i].v]==n+1) return 0;
				}
			}
		}
	}
	return true;
}

struct node {
	int dis,id;
};

bool operator<(node x,node y){
	return x.dis>y.dis;
}

void dijkstra(int x){
	priority_queue<node> q;
	d[x]=0;
	q.push({0,x});
	while(!q.empty()){
		node u=q.top();
		q.pop();
		if(vis[u.id]) continue;
		vis[u.id]=1;
		for(int i=head[u.id];i;i=e[i].nxt){
			if(d[e[i].v]>d[u.id]+e[i].w){
				d[e[i].v]=d[u.id]+e[i].w;
				q.push({d[e[i].v],e[i].v});
			}
		}
	}
}

int main(){
	memset(dis, inf, sizeof(dis));
	scanf("%d%d",&n,&m);
	FL(i,1,m){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	FL(i,1,n) add(n+1,i,0);
	bool flag=spfa(n+1);
	if(!flag){
		puts("-1");
		return 0;
	}
	FL(i,1,n){
		for(int j=head[i];j;j=e[j].nxt){
			e[j].w+=dis[i]-dis[e[j].v];
		}
	}
	FL(i,1,n){
		memset(d,inf,sizeof(d));
		memset(vis,0,sizeof(vis));
		dijkstra(i);
		ll ans=0;
		FL(j,1,n){
			if(d[j]==inf) ans+=1ll*1e9*j;
			else{
				ans+=1ll*(d[j]-dis[i]+dis[j])*j;
			}
		}
		printf("%lld\n", ans);
	}
	return 0;
}