P2505 [HAOI2012]道路

题意

• 有一个有向图

• 对每条边求出有多少条两个点对之间的最短路过这条边

点只有(10^3)，那么我们对每个点跑一遍最短路后，构建出最短路径树，所有在这棵树上的边就会算一遍贡献

具体的，求出有多少种走法从起点到边的一端，以及从另一端可以有多少条不同的路径，乘起来即可

#include<bits/stdc++.h>
#define For(i, a, b) for(int i = (a), en = (b); i <= en; ++i)
#define Rof(i, a, b) for(int i = (a), en = (b); i >= en; --i)
#define Tra(u, i) for(int i = hd[u]; ~i; i = e[i].net)
#define cst const
#define LL long long
#define DD double
#define LD long double
#define pb push_back
#define mp make_pair
#define fir first
#define sec second
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define eps 1e-12
#define maxn 5000
#define mod 1000000007
using namespace std;

int n, m, hd[maxn + 5], len = 0, as[maxn + 5];
struct Edge{int u, v, w, id, net;} e[maxn + 5];
void add(int u, int v, int w, int id){e[len] = (Edge){u, v, w, id, hd[u]}; hd[u] = len++;}

template <class T>
void read(T &x){
	char ch;
	bool ok;
	for(ok = 0, ch = getchar(); !isdigit(ch); ch = getchar()) if(ch == '-') ok = 1;
	for(x = 0; isdigit(ch); x = x * 10 + ch - '0', ch = getchar());
	if(ok) x = -x;
}

void add(int &x, int y){x += y; if(x >= mod) x -= mod;}

int dis[maxn + 5], f[maxn + 5];
priority_queue<pair<int, int> > q;
void dij(int s){
	memset(dis, inf, sizeof dis); dis[s] = 0;
	memset(f, 0, sizeof f); f[s] = 1;
	q.push(mp(0, s));
	while(q.size()){
		int u = q.top().sec, tem = -q.top().fir; q.pop();
		if(tem != dis[u]) continue;
		Tra(u, i){
			int v = e[i].v, w = e[i].w;
			if(dis[v] == dis[u] + w) add(f[v], f[u]);
			else if(dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				f[v] = f[u];
				q.push(mp(-dis[v], v));
			}
		}
	}
}
int g[maxn + 5];
int dfs(int u){
	if(g[u] != -1) return g[u];
	int asi = 1;
	Tra(u, i){
		int v = e[i].v, w = e[i].w;
		if(dis[u] + w != dis[v]) continue;
		add(asi, dfs(v));
	}
	return g[u] = asi;
}

int main(){
	//freopen("road.in", "r", stdin);
	//freopen("road.out", "w", stdout);
	memset(hd, -1, sizeof hd);
	read(n); read(m);
	For(i, 1, m){
		int u, v, w; read(u); read(v); read(w);
		add(u, v, w, i);
	}
	For(i, 1, n){
		dij(i);
		memset(g, -1, sizeof g);
		For(j, 0, len - 1){
			int u = e[j].u, v = e[j].v, w = e[j].w, id = e[j].id;
			if(dis[u] + w == dis[v]) add(as[id], 1ll * f[u] * dfs(v) % mod);
		}
	}
	For(i, 1, m) printf("%d
", as[i]);
	return 0;
}