刷题记录:牛客NC19987[HAOI2012]ROAD

传送门:牛客

题目描述:

C国有n座城市城市之间通过m条单向道路连接。一条路径被称为最短路当且仅当不存在从它的起
点到终点的另外一条路径总长度比它小。两条最短路不同当且仅当它们包含的道路序列不同。我们需
要对每条道路的重要性进行评估评估方式为计算有多少条不同的最短路经过该道路。现在这个任务
交给了你。
输入:
4 4
1 2 5
2 3 5
3 4 5
1 4 8
输出:
2
3
2
1

仅以此题作为我简单图论复健过程的休止符

一道最短路+拓扑排序的题目

主要思路:

1. 首先看完题面之后我们会发现我们需要的是关于最短路径的问题.所以我们最终的答案肯定是只跟最短路径有关的,所以我们可以预处理出最短路径图.对于最短路径图,我们可以直接跑最短路.我们固定一个源点$S$开始跑最短路,我们可以证明,对于一条边$<u,v>$,若$dis[v]==dis[u]+w[u][v]$的时候,我们这条边肯定属于我们的最短路径,反之则不属于.
   可以使用反证法来证明这一点,若满足上述条件的边不属于我们的最短路径,说明$u,v$直接存在一条更短的边来联通u,v两点,因为我们的dis[u]是S到u的最短距离,那么此时如果更短的边存在的话我们的dis[v]肯定会更小,就不满足我们的$dis[v]==dis[u]+w[u][v]$了
2. 那么当我们处理出最短路径图的时候.我们会发现对于一条边<u,v>来说,经过这条边的最短路径的数量肯定是等于源点到u的最短路径的数量$\ast$v到每一个最短路终点(当然也包括v自己)的最短路径的数量.对于源点到u的最短路径的数量,我们可以使用一种拓扑排序+dp的想法来求.对于一个v来说,到这个点的最短路径的数量显然等于所有能到达这个v点的u的最短路径数量之和.所以我们可以在最短路径图上直接开跑拓扑序,这就求出了正向的数量.对于反向的数量,我们需要倒着来跑拓扑排序.因为从一个点u出发到一个终点的最短路径的数量等于他能到达的所有点v到终点的最短路径的数量.所以我们需要先求出v再来递推求出u.此时需要注意的是,我们的u本身也是一个最短路的终点,所以到u的最短路径的数量等于v的所有最短路径的数量加上本身

还有一些需要注意的点:这道题需要求的是所有的最短路,所以我们需要跑N次最短路,那么我们最终的复杂度将为$nmlo{g}_{2}n$,不知道为什么在洛谷上竟然被卡了(没开O2时),所以洛谷上我们使用$Spfa$来跑,因为本题求出所有点的最短路,所以$Spfa$的均摊复杂度可以很好的体现出来,为$knm$.但是使用vector建边依旧会被洛谷卡,但是使用前向星建边则没有问题. 在牛客上则两种方法都没有问题

下面是具体的代码部分;

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define root 1,n,1
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
inline ll read() {
	ll x=0,w=1;char ch=getchar();
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') w=-1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x*w;
}
#define int long long
#define maxn 10000
const double eps=1e-8;
#define	int_INF 0x3f3f3f3f
#define ll_INF 0x3f3f3f3f3f3f3f3f
struct Edge{
	int v,w;
};
vector<Edge>edge[maxn],edge2[maxn];
int dis[maxn],vis[maxn];
int n,m;
//struct heapnode{
//	int u,d;
//	bool operator<(const heapnode &rhs) const {
//		return d>rhs.d;
//	}
//};
//void Dij(int S) {
//	for(int i=1;i<=n;i++) {
//		dis[i]=int_INF;vis[i]=0;
//	}
//	dis[S]=0;
//	priority_queue<heapnode>q;
//	q.push({S,0});
//	while(!q.empty()) {
//		heapnode f=q.top();q.pop();
//		int u=f.u;
//		if(vis[u]) continue;
//		vis[u]=1;
//		for(int i=0;i<edge[u].size();i++) {
//			int v=edge[u][i].v;
//			if(dis[v]>dis[u]+edge[u][i].w) {
//				dis[v]=dis[u]+edge[u][i].w;
//				q.push({v,dis[v]});
//			}
//		}
//	}
//}
void Spfa(int S) {
	queue<int>q;
	for(int i=1;i<=n;i++) {
		dis[i]=int_INF;vis[i]=0;
	}
	q.push(S);dis[S]=0;
	while(!q.empty()) {
		int u=q.front();q.pop();
		vis[u]=0;
		for(int i=0;i<edge[u].size();i++) {
			int v=edge[u][i].v;
			if(dis[v]>dis[u]+edge[u][i].w) {
				dis[v]=dis[u]+edge[u][i].w;
				if(!vis[v]) q.push(v);
			}
		}
	}
}
const int mod=1e9+7;
int in[maxn];int cnt1[maxn],cnt2[maxn];int topo_num[maxn],tot=0;
int U[maxn],V[maxn],W[maxn];int dis_map[maxn];
void topo(int S) {
	for(int u=1;u<=n;u++){
		in[u]=0;cnt1[u]=cnt2[u]=0;topo_num[u]=0;tot=0;
		edge2[u].clear();
	} 
	//建最短路图
	for(int i=1;i<=m;i++) {
		dis_map[i]=0;
		if(dis[V[i]]==dis[U[i]]+W[i]) {
			in[V[i]]++;
			dis_map[i]=1;
			edge2[U[i]].push_back({V[i],W[i]});
		}
	}
	//开始跑拓扑,正跑加倒跑
	queue<int>q;
	q.push(S);cnt1[S]=1;
	while(!q.empty()) {
		int u=q.front();q.pop();
		topo_num[++tot]=u;
		for(int i=0;i<edge2[u].size();i++) {
			int v=edge2[u][i].v;
			cnt1[v]=(cnt1[v]+cnt1[u])%mod;
			in[v]--;
			if(in[v]==0) q.push(v);
		}
	}
	for(int i=tot;i>=1;i--) {
		int u=topo_num[i];cnt2[u]++;
		for(int j=0;j<edge2[u].size();j++) {
			int v=edge2[u][j].v;
			cnt2[u]=(cnt2[u]+cnt2[v])%mod;
		}
	}
}
int ans[maxn];
void solve(int S) {
	Spfa(S);topo(S);
	for(int i=1;i<=m;i++) {
		if(dis_map[i])
			ans[i]=(ans[i]+cnt1[U[i]]*cnt2[V[i]]%mod)%mod;
	}
}
signed main() {
	n=read();m=read();
	for(int i=1;i<=m;i++) {
		U[i]=read(),V[i]=read();W[i]=read();
		edge[U[i]].push_back({V[i],W[i]});
	}
	for(int i=1;i<=n;i++) {
		solve(i);
	}
	for(int i=1;i<=m;i++) {
		printf("%d\n",ans[i]);
	}
	return 0;
}