记录编号	393691	评测结果	AAAAAAAAAA
题目名称	[HAOI 2012]道路	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	1.134 s
提交时间	2017-04-11 21:20:28	内存使用	0.42 MiB

#include <bits/stdc++.h>
#define MAXN 1523
#define MAXM 5023
using namespace std;
const int mod = 1e9 + 7;

inline void File_Read() {
#ifdef MYLAB
	freopen("in.txt", "r", stdin);
#else 
	freopen("roadsw.in", "r", stdin);
	freopen("roadsw.out", "w", stdout);
#endif
}

inline int get_num() {
	int k = 0; char c = getchar();
	for(;!isdigit(c); c = getchar());
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k;
}

struct edge {
	int to, ne, v;
	edge(){;}
	edge(int to_, int ne_, int v_) {
		to = to_;
		ne = ne_;
		v = v_;
	}
}e[MAXM];

int en, head[MAXN], n, m, cnt[MAXN], dis[MAXN], num[MAXM], sum[MAXN];
bool in_que[MAXN];

inline void addedge(int fr, int to, int v){
	e[++en] = edge(to, head[fr], v); head[fr] = en;
}

inline void dij(int be) {
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > q;
	q.push(make_pair(0, be));
	dis[be] = 0;
	cnt[be] = 1;
	int now, v;
	while(!q.empty()) {
		now = q.top().second; v = q.top().first;
		q.pop();
		if(v > dis[now]) continue;
		for(int i = head[now]; i; i = e[i].ne) {
			int to = e[i].to;
			if(dis[to] > dis[now] + e[i].v) {
				dis[to] = dis[now] + e[i].v;
				cnt[to] = cnt[now];
				q.push(make_pair(dis[to], to));
			} else if(dis[to] == dis[now] + e[i].v) {
				cnt[to] += cnt[now];
				cnt[to] %= mod;
			}
			
		}
	}
}

int dfs(int x) {
	if(sum[x]) return sum[x]; //sum[x]指的是经过点x的最短路的数量 
	sum[x] = 1;
	for(int i = head[x]; i; i = e[i].ne) {
		int y = e[i].to;
		int z = e[i].v;
		if(dis[y] != dis[x] + z) continue;
		sum[x] += dfs(y);
		num[i] += sum[y] * cnt[x];
		num[i] %= mod; 
	}
	return sum[x];
}

int main() {
	File_Read();
	n = get_num();
	m = get_num();
	for(int i = 1; i <= m; i++) {
		int fr = get_num();
		int to = get_num();
		int v = get_num();
		addedge(fr, to, v);
	}
	for(int i = 1; i <= n; i++) {
		memset(cnt, 0, sizeof(cnt));
		memset(dis, 64, sizeof(dis));
		memset(sum, 0, sizeof(sum));
		dij(i);
		dfs(i);
	}
	for(int i = 1; i <= m; i++) printf("%d\n", num[i]);
	
}