题解 SP3545 【NAJKRACI

题目链接

Solution Najkraci

题目大意:给定一个有向图，对于每条边，求出有多少条最短路包括这条边

最短路，动态规划，计数

---

分析:

由于(n)范围较小，我们可以枚举最短路的源点，然后显然在最短路边上的边构成了一个(DAG)，我们在(DAG)上做(dp)就好

我们记(to[u])表示在(DAG)上源点有多少条路径到达(u)，(from[u])表示在(DAG)上从(u)出发有多少条路径到达其它点

记源点为(s),(to[s]=1)，假设有向边为((u,v))，那么(to[v] = sum to[u])

同理(from[u]=sum from[v]+1)(因为(u)点到自己的路径也要纳入其中)

然后一条边((u,v))以(s)为源点时被最短路包括的次数就是(to[u] imes from[v])

(to)可以在跑(Dijkstra)的时候计算，有个(Trick)就是每次(u)松弛(v)的时候把(to[v])重置为(0)，因为(u)松弛(v)后前面松弛过(v)的边不可能成为(DAG)的一部分

(from)以跑(Dijkstra)顺序的逆序计算即可

枚举源点跑(n)次(Dijkstra)即可得出答案

#include <cstdio>
#include <cctype>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn = 2e3,maxm = 2e4,mod = 1e9 + 7;
inline int read(){
	int x = 0;char c = getchar();
	while(!isdigit(c))c = getchar();
	while(isdigit(c))x = x * 10 + c - '0',c = getchar();
	return x;
}
struct Edge{
	int from,to,dis;
}Edges[maxm];
int head[maxn],nxt[maxm],tot = 1,n,m;
inline void addedge(int from,int to,int dis){
	Edges[++tot] = Edge{from,to,dis};
	nxt[tot] = head[from];
	head[from] = tot;
}
ll ans[maxm],from[maxn],to[maxn];
int dis[maxn],vis[maxn];
vector<int> topo;
struct HeapNode{
	int u,h;
	bool operator < (const HeapNode &rhs)const{
		return h > rhs.h;
	}
};
priority_queue<HeapNode> Q;
inline void dijkstra(int s){
	memset(from,0,sizeof(from));
	memset(to,0,sizeof(to));
	memset(vis,0,sizeof(vis));
	memset(dis,0x3f,sizeof(dis));
	dis[s] = 0,to[s] = 1;topo.clear();
	Q.push(HeapNode{s,dis[s]});
	while(!Q.empty()){
		int u = Q.top().u;Q.pop();
		if(vis[u])continue;
		vis[u] = 1;
		topo.push_back(u);
		for(int i = head[u];i;i = nxt[i])
			if(!(i & 1)){
				const Edge &e = Edges[i];
				if(dis[e.from] + e.dis > dis[e.to])continue;//有重边
				if(dis[e.from] + e.dis < dis[e.to]){
					to[e.to] = 0;
					dis[e.to] = dis[e.from] + e.dis;
					Q.push(HeapNode{e.to,dis[e.to]});
				}
				to[e.to] = (to[e.to] + to[u]) % mod;
			}
	}
	for(auto it = topo.rbegin();it != topo.rend();it++){
		from[*it]++;
		for(int i = head[*it];i;i = nxt[i])
			if(i & 1){
				const Edge &e = Edges[i];
				if(dis[e.to] + e.dis == dis[e.from])
					from[e.to] += from[*it],from[e.to] %= mod;
			}
	}
	for(int i = 2;i <= tot;i += 2){
		const Edge &e = Edges[i];
		if(dis[e.from] + e.dis == dis[e.to])ans[i >> 1] += to[e.from] * from[e.to],ans[i >> 1] %= mod;
	}
}
int main(){
	n = read(),m = read();
	for(int u,v,d,i = 1;i <= m;i++)
		u = read(),v = read(),d = read(),addedge(u,v,d),addedge(v,u,d);
	for(int i = 1;i <= n;i++)dijkstra(i);
	for(int i = 1;i <= m;i++)
		printf("%lld
",ans[i]);
	return 0;
}