https://www.luogu.com.cn/record/39193821

最慢的一个点 1.07s，但是 SF 说最慢的一个点才 500ms。

#include<cstdio>
#include<algorithm>
#include<vector>
#include<queue>
#define int long long
using namespace std;
int n,m,S,vis[3010],inque[3010],high[3010],dis[3010][3010];
struct E{
	int from,to,wei;
	E(int f,int t=0,int w=0) { from=f; to=t; wei=w; }
	bool operator<(const E&a)const{
		return dis[S][from]+wei>dis[S][a.from]+a.wei;
	}
};
vector<E>edge[3010];
queue<int>que;
signed main(){
    scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) high[i]=1e9;
	for(int i=1;i<=m;i++){
		int u,v,w; scanf("%lld%lld%lld",&u,&v,&w);
		edge[u].push_back(E(u,v,w));
	}
	S=n+1;
	for(int i=1;i<=n;i++) edge[S].push_back(E(S,i,0));
	que.push(S); high[S]=0;
	while(!que.empty()){
		int u=que.front(); que.pop(); inque[u]=0;
		vis[u]++; if(vis[u]>=n) { printf("-1\n"); return 0; }
		for(int i=0;i<edge[u].size();i++){
			E v=edge[u][i];
			if(high[v.to]>high[u]+v.wei){
				high[v.to]=high[u]+v.wei;
				if(!inque[v.to]) { que.push(v.to); inque[v.to]=1; }
			}
		}
	}
	for(int u=1;u<=n;u++)
		for(int i=0;i<edge[u].size();i++){
			E&v=edge[u][i];
			v.wei+=high[v.from]-high[v.to];
		}
	for(S=1;S<=n;S++){
		priority_queue<E>pq;
		pq.push(E(0,S,1));
		while(!pq.empty()){
			E u=pq.top(); pq.pop();
			if(dis[S][u.to]) continue;
			dis[S][u.to]=dis[S][u.from]+u.wei;
			for(int i=0;i<edge[u.to].size();i++)
				pq.push(edge[u.to][i]);
		}
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			if(!dis[i][j]) dis[i][j]=1e9;
			else dis[i][j]+=high[j]-high[i]-1;
	for(int i=1;i<=n;i++){
		int ans=0;
		for(int j=1;j<=n;j++) ans+=j*dis[i][j];
		printf("%lld\n",ans);
	}
	return 0;
}