第8,9,11超时求调

#include<bits/stdc++.h>
using namespace std;
const int MAXN=3007;
int tp[MAXN],mp=0;
struct node{
	int val,nxt,len;
};
node mar[MAXN*2];
int times[MAXN];
void con(int a,int b,int c){
	mar[++mp].val=b;
	mar[mp].len=c;
	mar[mp].nxt=tp[a];
	tp[a]=mp;
}
int dis[MAXN],n,m;
bool in[MAXN];
bool spfa(int st){
	dis[st]=0;
	queue<int> q;
	q.push(st);
	in[st]=1;
	int hd,pos;
	while(!q.empty()){
		hd=q.front();
		pos=tp[hd];
		while(pos!=0){
			if(mar[pos].len+dis[hd]<dis[mar[pos].val]){
				dis[mar[pos].val]=mar[pos].len+dis[hd];
				if(!in[mar[pos].val]){
					times[mar[pos].val]++;
					if(times[mar[pos].val]>n+1)return 0;
					q.push(mar[pos].val);
					in[mar[pos].val]=1;
				}
			}
			pos=mar[pos].nxt;
		}
		in[hd]=0;
		q.pop();
	}
	return 1;
}
struct note{
	int pos,len;
	bool operator < (const note &b)const{
		return len>b.len;
	}
};
bool flag[MAXN];
int ddis[MAXN];
void dj(int st){
	int hd,pos;
	priority_queue<note> q;
	q.push(note{st,0});
	while(!q.empty()){
		hd=q.top().pos;
		q.pop();
		pos=tp[hd];
		if(flag[hd])continue;
		flag[hd]=1;
		while(pos!=0){
			if(ddis[hd]+mar[pos].len<ddis[mar[pos].val]){
				ddis[mar[pos].val]=ddis[hd]+mar[pos].len;
				//flag[mar[pos].val]=1;
				if(!flag[mar[pos].val])q.push(note{mar[pos].val,ddis[mar[pos].val]});
			}
			pos=mar[pos].nxt;
		}
	}
}
int main(){
	ios::sync_with_stdio(false);
	int a,b,c;
	long long ans=0;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&a,&b,&c);
		con(a,b,c);
	}
	for(int i=1;i<=n;i++)con(n+1,i,0);
	for(int i=1;i<=n+1;i++)dis[i]=1e9;
	if(!spfa(n+1)){
		printf("-1\n");
		return 0;
	};
	for(int i=1;i<=n;i++){
		for(int pos=tp[i];pos!=0;pos=mar[pos].nxt){
			mar[pos].len+=dis[i]-dis[mar[pos].val];
			//printf("%d--->%d new:%d \n",i,mar[pos].val,mar[pos].len);
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++)ddis[j]=1e9;
		memset(flag,0,sizeof(bool)*(n+2));
		ddis[i]=0;	
		dj(i);
		ans=0;
		/*for(int j=1;j<=n;j++){
			//ans+=j*ddis[j];
			printf("%d ",ddis[j]+dis[j]-dis[i]);
		}
		printf("\n");*/
		for(int j=1;j<=n;j++){
			if(ddis[j]==1e9)ans+=j*1e9;
			else ans+=j*(ddis[j]+dis[j]-dis[i]);
		}
		printf("%lld\n",ans);
	}
}