记录编号	444781	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]道路	最终得分	100
用户昵称	rvalue	是否通过	通过
代码语言	C++	运行时间	1.200 s
提交时间	2017-09-04 10:25:11	内存使用	0.54 MiB

#include <queue>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>

const int MAXV=1510;
const int MAXE=5010;
const int MOD=1e9+7;

struct Edge{
	int from;
	int to;
	int dis;
	int cnt;
	Edge* next;
};
Edge E[MAXE];
Edge R[MAXE];
Edge* head[MAXV];
Edge* headr[MAXV];
Edge* top=E;
Edge* topr=R;

int v;
int e;
int a[MAXV];
int r[MAXV];
int dis[MAXV];
bool visited[MAXV];

void SPFA(int);
void DFS(int);
void DFSR(int);
void Initialize();
void Insert(int,int,int);
void RInsert(int,int,int);

int main(){
	Initialize();
	for(int i=1;i<=v;i++){
		SPFA(i);
		memset(a,0,sizeof(a));
		DFS(i);
		memset(r,0,sizeof(r));
		r[i]=1;
		for(int i=1;i<=v;i++)
			DFSR(i);
		for(int k=1;k<=v;k++){
			for(Edge* i=head[k];i!=NULL;i=i->next){
				if(dis[i->to]==dis[k]+i->dis){
					i->cnt=(r[k]*a[i->to]%MOD+i->cnt)%MOD;
				}
			}
		}
	}
	for(Edge* i=E;i!=top;i++){
		printf("%d\n",i->cnt);
	}
	return 0;
}

void DFS(int root){
	// printf("DFS: %d\n",root);
	if(a[root]!=0)
		return;
	else{
		a[root]=1;
		for(Edge* i=head[root];i!=NULL;i=i->next){
			if(dis[i->to]==dis[root]+i->dis){
				DFS(i->to);
				a[root]+=a[i->to];
			}
		}
	}
}

void DFSR(int root){
	// printf("DFSR: %d\n",root);
	if(r[root]!=0)
		return;
	else{
		for(Edge* i=headr[root];i!=NULL;i=i->next){
			if(dis[i->to]+i->dis==dis[root]){
				DFSR(i->to);
				r[root]+=r[i->to];
			}
		}
	}
}

void SPFA(int root){
	memset(visited,0,sizeof(visited));
	memset(dis,0x3F,sizeof(dis));
	std::queue<int> q;
	q.push(root);
	dis[root]=0;
	// visited[root]=true;
	while(!q.empty()){
		root=q.front();
		q.pop();
		visited[root]=false;
		for(Edge* i=head[root];i!=NULL;i=i->next){
			if(dis[i->to]>dis[root]+i->dis){
				dis[i->to]=dis[root]+i->dis;
				if(!visited[i->to]){
					visited[i->to]=true;
					q.push(i->to);
				}
			}
		}
	}/*
	for(int i=1;i<=v;i++)
		printf("%d ",dis[i]);
	putchar('\n');*/
}

void Initialize(){
#ifndef ASC_LOCAL
	freopen("roadsw.in","r",stdin);
	freopen("roadsw.out","w",stdout);
#endif
	int from,to,dis;
	scanf("%d%d",&v,&e);
	for(int i=0;i<e;i++){
		scanf("%d%d%d",&from,&to,&dis);
		Insert(from,to,dis);
		RInsert(to,from,dis);
	}
}

inline void Insert(int from,int to,int dis){
	top->to=to;
	top->cnt=0;
	top->dis=dis;
	top->from=from;
	top->next=head[from];
	head[from]=top;
	top++;
}

inline void RInsert(int from,int to,int dis){
	topr->to=to;
	topr->cnt=0;
	topr->dis=dis;
	topr->from=from;
	topr->next=headr[from];
	headr[from]=topr;
	topr++;
}