记录编号	152971	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]道路	最终得分	100
用户昵称	水中音	是否通过	通过
代码语言	C++	运行时间	1.187 s
提交时间	2015-03-16 11:13:05	内存使用	0.45 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define MOD 1000000007
#define N 1510
#define M 5010
#define INF 1e9
int n,m,i,p,j,zj1,zj2,zj3;
int ans[M]={0};

int to[M]={0},fr[M]={0},head[N]={0},ne[M]={0},w[M]={0},sj=0;
inline void addedge(int u,int v,int z)
{to[++sj]=v,fr[sj]=u,ne[sj]=head[u],head[u]=sj,w[sj]=z;}

void init()
{
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d",&zj1,&zj2,&zj3);
		addedge(zj1,zj2,zj3);
	}
}

int que[N]={0},qhead=1,qtail=0;bool flag[N]={0};
inline int GET()
{int x=que[qhead];que[0]--,flag[x]=0;if(++qhead==N)qhead=1;return x;}
inline void PUSH(int x)
{que[0]++,flag[x]=1;if(++qtail==N)qtail=1;que[qtail]=x;}

int dis[N]={0};
inline void spfa(int x)
{
	for(i=1;i<=n;i++)dis[i]=INF;dis[x]=0,PUSH(x);
	while(que[0])
	for(zj1=GET(),i=head[zj1];i;i=ne[i])
	if((zj2=dis[zj1]+w[i])<dis[to[i]])
	{dis[to[i]]=zj2;if(!flag[to[i]])PUSH(to[i]);}
}

int s[N]={0};bool flags[N]={0};
inline void GET_s(int x)
{
	flags[x]=1;
	for(int h=head[x];h;h=ne[h])
	if(dis[to[h]]==dis[x]+w[h])
	{s[to[h]]++;if(!flags[to[h]])GET_s(to[h]);}
}

int frs[N]={0};bool str[M]={0};
inline void GET_frs(int x)
{
	for(int h=head[x];h;h=ne[h])
	if(dis[to[h]]==dis[x]+w[h])
	{
		str[h]=1;frs[to[h]]+=frs[x];
		while(frs[to[h]]>=MOD)frs[to[h]]-=MOD;
		if(!(--s[to[h]]))GET_frs(to[h]);
	}
} 

int tos[N]={0};
inline void GET_tos(int x)
{
	tos[x]=1;
	for(int h=head[x];h;h=ne[h])
	if(dis[to[h]]==dis[x]+w[h])
	{
		if(!tos[to[h]])GET_tos(to[h]);
		tos[x]+=tos[to[h]];
		while(tos[x]>=MOD)tos[x]-=MOD;
	}
}

void work()
{
	for(j=1;j<=n;j++)
	{
		spfa(j);GET_s(j);frs[j]=1,GET_frs(j);GET_tos(j);
		for(i=1;i<=sj;i++)if(str[i])
		ans[i]+=frs[fr[i]]*tos[to[i]],ans[i]%=MOD;
		memset(flags,0,sizeof(flags));memset(str,0,sizeof(str));
		memset(frs,0,sizeof(frs));memset(tos,0,sizeof(tos));
	}
	for(i=1;i<=m;i++)
	printf("%d\n",ans[i]);
}
int main()
{
	freopen("roadsw.in","r",stdin);
	freopen("roadsw.out","w",stdout);
	init();
	work();
	return 0;
}