记录编号	314281	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]道路	最终得分	100
用户昵称	NewBee	是否通过	通过
代码语言	C++	运行时间	1.481 s
提交时间	2016-10-02 21:45:30	内存使用	3.03 MiB

#include<cstdio>
#include<queue>
#include<cstring>
#define Cu fclose(stdin);fclose(stdout);return 0;
#define Begin freopen("roadsw.in","r",stdin);freopen("roadsw.out","w",stdout); chul();Cu
using namespace std;
const int maxn=50010;
const int mod=1000000007;
struct op{
	int to,next,pay,num;
}r[maxn<<1];
int head[maxn],tim,dis[maxn],d[maxn],gx[maxn],rhead[maxn],a[maxn];int m,n;
bool flag[maxn];
queue<int> q;
void insert(int fr,int to,int pa,int num){
	tim++;
	r[tim].to=to;
	r[tim].num=num;
	r[tim].next=head[fr];
	r[tim].pay=pa;
	head[fr]=tim;
}
void reinsert(int fr,int to,int pa){
	tim++;
	r[tim].to=to;
	r[tim].next=rhead[fr];
	r[tim].pay=pa;
	rhead[fr]=tim;
}
void spfa(int rt){
	queue<int> q;
	memset(dis,0x7f,sizeof(dis));
	memset(flag,0,sizeof(flag));
	dis[rt]=0;
	int x,y;
	q.push(rt);
	while(!q.empty()){
		x=q.front();
		q.pop();
		flag[x]=0;
		for(int i=head[x];i;i=r[i].next){
			y=r[i].to;
			if(dis[y]>dis[x]+r[i].pay){
				dis[y]=dis[x]+r[i].pay;
				if(!flag[y]){
					flag[y]=1;
					q.push(y);
				}
			}
		}
	}
}
void geta(int rt){
	if(a[rt])return;
	int y;
	for(int i=rhead[rt];i;i=r[i].next){
		y=r[i].to;
		if(dis[y]+r[i].pay==dis[rt]){
			geta(y);
			a[rt]+=a[y];
		}
	}
}
void getd(int rt){
	if(d[rt]>0)return;
	int y;
	d[rt]=1;
	for(int i=head[rt];i;i=r[i].next){
		y=r[i].to;
		if(dis[y]==dis[rt]+r[i].pay){
			getd(y);
			d[rt]+=d[y];
		}
	}
}
void clean(int rt){
	memset(d,0,sizeof(d));
	memset(a,0,sizeof(a));
	spfa(rt);
	int y;
	getd(rt);
	a[rt]=1;
	for(int i=1;i<=n;i++)geta(i);
	for(int i=1;i<=n;i++){
		for(int j=head[i];j;j=r[j].next){
			y=r[j].to;
			if(dis[y]==dis[i]+r[j].pay){
				gx[r[j].num]+=(a[i]*d[y]);
				gx[r[j].num]%=mod;
			}
		}
	}
}
void chul(){
	scanf("%d%d",&n,&m);
	int x,y,z;
	for(int i=1;i<=m;i++){
		scanf("%d%d%d",&x,&y,&z);
		insert(x,y,z,i);
		reinsert(y,x,z);
	}
	for(int i=1;i<=n;i++)clean(i);
	for(int i=1;i<=m;i++)printf("%d\n",gx[i]);
}
int main(){
	Begin;
}
/*
4 4
1 2 5
2 3 5
3 4 5
1 4 8

*/