记录编号	314309	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]道路	最终得分	100
用户昵称	小e	是否通过	通过
代码语言	C++	运行时间	1.579 s
提交时间	2016-10-03 06:29:01	内存使用	0.40 MiB

#include "cstdio"
#include "cstring"
#include "iostream"
#include "queue"
using namespace std;

typedef long long LL;
const int mod = 1000000007;
int n, m;
struct Edge
{
	int from, to, w;
	int next;
}edges[5100];
struct Node
{
	int pos, dist;
	inline Node(const int& a, const int& b)
	{
		pos = a; dist = b;
	}
	inline bool operator < (const Node& a) const
	{
		return dist > a.dist;
	}
};
int head[1600], tot;
int dis[1600];
int in[1600], out[1600], indegree[1600], outdegree[1600];
// in[i]: 最短路径上从起点走到点i的方案数  out[i]: 从i出发的最短路径条数
int ans[5100];

inline void Read(int& a)
{
	a = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9'){
		a = a * 10 + ch - '0';
		ch = getchar();
	}
}

inline void AddEdge(const int& from, const int& to, const int& w)
{
	edges[++tot].from = from;
	edges[tot].to = to;
	edges[tot].w = w;
	edges[tot].next = head[from];
	head[from] = tot;
}

inline void Dijkstra(const int& s)
{
	priority_queue <Node> Q;
	memset(dis, 0x3f, sizeof(dis));
	dis[s] = 0;
	Q.push(Node(s, 0));
	while(!Q.empty()){
		Node top = Q.top(); Q.pop();
		int pos = top.pos, dist = top.dist;
		if(dist != dis[pos]) continue;
		for(int i = head[pos]; i; i = edges[i].next){
			int to = edges[i].to, w = edges[i].w;
			if(dis[to] > dis[pos] + w){
				dis[to] = dis[pos] + w;
				Q.push(Node(to, dis[to]));
			}
		}
	}
}

inline void Topo(const int& s)
{
	memset(in, 0, sizeof(in));
	memset(indegree, 0, sizeof(indegree));
	memset(outdegree, 0, sizeof(outdegree));
	queue <int> Q;
	for(int j = 1; j <= m; j++){
		int from = edges[j].from, to = edges[j].to, w = edges[j].w;
		if(dis[to] == dis[from] + w){
			// 第j条边在从i到to的最短路上
			indegree[to]++; outdegree[from]++;
		}
	}
	in[s] = 1;
	Q.push(s);
	while(!Q.empty()){
		int front = Q.front(); Q.pop();
		for(int i = head[front]; i; i = edges[i].next){
			int from = edges[i].from, to = edges[i].to, w = edges[i].w;
			if(dis[to] == dis[from] + w){
				in[to] = (in[to] + in[from]) % mod;
				indegree[to]--;
				if(!indegree[to]) Q.push(to);
			}
		}	
	}
	// printf("s:%d\n", s);
	// for(int i = 1; i <= n; i++)
	// 	printf("in[%d]:%d\n", i, in[i]);
	// puts("");
}

void DFS(const int& a)
{
	if(out[a]) return;
	out[a] = 1;
	for(int i = head[a]; i; i = edges[i].next){
		int from = edges[i].from, to = edges[i].to, w = edges[i].w;
		if(dis[to] == dis[from] + w){
			DFS(to);
			out[a] = (out[a] + out[to]) % mod;
		}
	}
}

int main()
{
#define SUBMIT
#ifdef SUBMIT
	freopen("roadsw.in", "r", stdin); freopen("roadsw.out", "w", stdout);
#endif

	Read(n); Read(m);
	int from, to, w;
	for(int i = 1; i <= m; i++){
		Read(from); Read(to); Read(w);
		AddEdge(from, to, w);
	}

	for(int i = 1; i <= n; i++){
		Dijkstra(i);
		Topo(i);
		memset(out, 0, sizeof(out));
		for(int j = 1; j <= m; j++){
			int from = edges[j].from, to = edges[j].to, w = edges[j].w;
			if(dis[to] == dis[from] + w){
				DFS(to);
				ans[j] = (ans[j] + (LL)(in[from] * out[to])) % mod;
			}
		}
	}

	for(int i = 1; i <= m; i++)
		printf("%d\n", ans[i] % mod);

#ifndef SUBMIT
	printf("\n----------\n");
	getchar(); getchar();
#else
	fclose(stdin); fclose(stdout);
#endif
	return 0;				
}
 /*
	样例输入
	4 4
	1 2 5
	2 3 5
	3 4 5
	1 4 8
	样例输出
	2
	3
	2
	1
 */
 /*
	4 4
	1 2 6
	1 3 2
	3 2 4
	2 4 2 
 */