记录编号	314135	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]道路	最终得分	100
用户昵称	LOSER	是否通过	通过
代码语言	C++	运行时间	1.422 s
提交时间	2016-10-02 18:04:14	内存使用	0.94 MiB

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 5010
#define mod 1000000007
int n,m;
struct Edge{int to,next,from,dis;}e[maxn<<1],a[maxn<<1],d[maxn<<1];
int len,head[maxn],lena,lend,headd[maxn],heada[maxn];
void Insert(int x,int y,int z){
	e[++len].to=y;
	e[len].from=x;
	e[len].dis=z;
	e[len].next=head[x];
	head[x]=len;
}
void Addedge_a(int x,int y,int z){
	a[++lena].to=y;
	a[lena].from=x;
	a[lena].dis=z;
	a[lena].next=heada[x];
	heada[x]=lena;	
}
void Addedge_d(int x,int y,int z){
	d[++lend].to=y;
	d[lend].from=x;
	d[lend].dis=z;
	d[lend].next=headd[x];
	headd[x]=lend;
}
struct Node{
	int num,dis;	
	Node(int A,int B){num=A, dis=B;}
	bool operator < (const Node & a)const{
		return dis>a.dis;	
	}
};
int dis[maxn];
void Dijkstra(int x){
	bool flag[maxn]={0};
	memset(dis,0x7f,sizeof(dis)); dis[x]=0; 
	priority_queue<Node> q; q.push(Node(x,0));
	while( !q.empty() ){
		Node temp=q.top(); q.pop();
		int u=temp.num; flag[u]=1;
		for(int i=head[u];i;i=e[i].next){
			int v=e[i].to;
			if(!flag[v] && dis[v]>dis[u]+e[i].dis){
				dis[v]=dis[u]+e[i].dis;	
				q.push(Node(v,dis[v]));
			}	
		}
	}
}
int ad[maxn],aa[maxn],f1[maxn],f2[maxn];
int Work_f1(int x){
	if(f1[x])return f1[x];
	bool flag=0;
	for(int i=headd[x];i;i=d[i].next){
		int y=d[i].to;
		//printf("-%d--%d\n",x,y);
		f1[x]+=Work_f1(y);
		flag=1;
	}
	if(!flag)f1[x]=1;
	return f1[x];	
}
int Work_f2(int x){
	if(f2[x])return f2[x];
	f2[x]=1;
	for(int i=heada[x];i;i=a[i].next){
		int y=a[i].to;
		f2[x]+=Work_f2(y);
	}
	return f2[x];
}
int Ans[maxn];
bool Check[maxn];
void Work(int x){
#define u e[i].from
#define v e[i].to
	Dijkstra(x);
	memset(Check,0,sizeof(Check));
	memset(f1,0,sizeof(f1)); 
	memset(f2,0,sizeof(f2));
	memset(a,0,sizeof(a)); memset(heada,0,sizeof(heada)); lena=0;
	memset(d,0,sizeof(d)); memset(headd,0,sizeof(headd)); lend=0;
	memset(aa,0,sizeof(aa)); memset(ad,0,sizeof(ad));
	//for(int i=1;i<=n;i++)printf("%d\n",dis[i]);
	for(int i=1;i<=len;i++){
		if(dis[u]+e[i].dis==dis[v]){
			Check[i]=1;
			Addedge_a(u,v,e[i].dis);  aa[v]++;
			Addedge_d(v,u,e[i].dis);  ad[u]++;
		}
	}
	for(int i=1;i<=lena;i++){
	//	printf("---%d %d---\n",a[i].from,a[i].to);
	}
	for(int i=1;i<=n;i++)if(!ad[i])Work_f1(i);
	Work_f2(x);//f2为出 f1为入 
	for(int i=1;i<=n;i++){
		//printf("<<%d>>\n",f1[i]);	
	}
	for(int i=1;i<=len;i++){
		if(Check[i]){
		//	printf("---%d %d\n",u,v);
			Ans[i]+=f1[u]*f2[v];
			Ans[i]%=mod;	
		}
	}
#undef u
#undef v
}
int main(){
	freopen("roadsw.in","r",stdin); freopen("roadsw.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,z; scanf("%d%d%d",&x,&y,&z);
		Insert(x,y,z);	
	}
	for(int i=1;i<=n;i++)Work(i);	
	for(int i=1;i<=m;i++){
		Ans[i]%=mod;
		printf("%d\n",Ans[i]);	
	}
	getchar(); getchar();
	return 0;	
} 
/*
4 4
1 2 5
2 3 5
3 4 5
1 4 8
*/