本题为3月17日23上半学期集训每日一题中B题的题解
题面
题目描述
在顺利攻破 Lord lsp 的防线之后,lqr 一行人来到了 Lord lsp 的城堡下方。Lord lsp 黑化之后虽然拥有了强大的超能力,能够用意念力制造建筑物,但是智商水平却没怎么增加。现在 lqr 已经搞清楚黑暗城堡有 N 个房间,M 条可以制造的双向通道,以及每条通道的长度。
lqr 深知 Lord lsp 的想法,为了避免每次都要琢磨两个房间之间的最短路径,Lord lsp 一定会把城堡修建成树形的;但是,为了尽量提高自己的移动效率,Lord lsp 一定会使得城堡满足下面的条件:
设 (D_i) 为如果所有的通道都被修建,第 i 号房间与第 1 号房间的最短路径长度;而 (S_i) 为实际修建的树形城堡中第 i 号房间与第 1 号房间的路径长度,对于所有满足 (1leq ileq N) 的整数 i,有 (S_i = D_i) 。
为了打败 Lord lsp,lqr 想知道有多少种不同的城堡修建方案。于是 lqr 向 applepi 提出了这个问题。由于 applepi 还要忙着出模拟赛,所以这个任务就交给你了。当然,你只需要输出答案对 (2^{31} – 1) 取模之后的结果就行了
输入
第一行有两个整数 N 和 M。 之后 M 行,每行三个整数 X,Y 和 L,表示可以修建 X 和 Y 之间的一条长度为 L 的通道。
输出
输出一个整数,表示答案对 (2^{31} – 1) 取模之后的结果。
样例输入
3 3
1 2 2
1 3 1
2 3 1
样例输出
2
提示
对于 30% 的数据,(2leq Nleq 5) ,(Mleq 10) 。
对于 50% 的数据,满足条件的方案数不超过 10000。
对于 100% 的数据,(2leq Nleq 1000),(N – 1leq Mleq frac{Ntimes (N – 1)}{2}),(1 leq Lleq 100)。
思路分析
本题题目的意思是说,给你一张图,让你选择其中的几条边来组成一个生成树
,这个生成树中的点需要满足到节点1的最短距离与原本到节点1的最短距离一致.
换句话说,这个生成树中是以每个节点到节点1的路径就是原本图中的最短路径组成的.这种生成树我们称之为最短路径树
(不要管oj上这题的tag).所以这道题就是让我们求原图有几个最短路径树
.此题没有负权边,想要求解一颗这样的最短路径树
,其实只要使用Dijkstra算法
即可.
如果你不知道什么是Dijkstra算法
,请自行搜索学习,比如阅读这篇博客.然后独立通过洛谷上的这道模板题,以确保你已学会.
根据Dijkstra算法
的运行过程可知,在以一个点为起点跑完Dijkstra算法
以后,我们会得到以这个点为起点,到图上所有点的一条最短路径.而根据最短路径的定义可知,一个图上所有最短路径的集合必然是原图的一颗生成树.这里简单说明一下:
- 首先,在由最短路径组成的图形中,一定不会出现正环,因为沿着正环路径一定变长,不会组成最短路的一部分.
- 其次,不会出现在一个点分出的两条路径在另一个点上合并,因为最短路径长度一定是一样的,而Dijkstra只会找出从起点到每一个点的一条最短路径.
但是这题不是让我们求原图的一颗最短路径树
,而是让我们求原图一共有多少种最短路径树
,所以我们还需要知道什么时候会产生多棵树.其实在前面分析中已经出现产生多棵树的原因了,那就是在两个点之间出现了多条边和这两点间的最短路径长度相等(注意,是边,不是路径,因为后续会用分步乘法计数原理
来计算总数,而路径是由边来产生的,所以会自动计算出路径数).正是因为有这样的边,所以我们在产生最短路径的时候可以有多种选择,也就会有多种最短路径树
.而Dijkstra算法
本身只选择了其中之一.所以要求总数,我们只需要再维护出两个点之间有多少条和最短路径长度相等的边,然后利用分步乘法计数原理
把它们乘起来即可.
参考代码
时间复杂度: (O(MlogN))
空间复杂度: (O(N + M))
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")
#include
using namespace std;
using i64 = long long;
/*
边对象
*/
struct edge {
int to;
int cost;
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n, m;
cin >> n >> m;
vector> g(n, vector()); // 邻接表
// 输入各个边,构建邻接表
while (m--) {
int x, y, l;
cin >> x >> y >> l;
x--;
y--;
g[x].push_back({y, l});
g[y].push_back({x, l}); // 无向图
}
// 优先队列(二叉堆)优化的Dijkstra模板.如果你不会优先队列优化,在这题里写一个普通的Dijkstra应该也是可以的,但是推荐写优先队列优化的Dijkstra
priority_queue> que;
int *d = new int[n];
memset(d, 0x3f, sizeof(int) * n);
d[0] = 0;
que.push({d[0], 0});
while (!que.empty()) {
int u = que.top().second;
que.pop();
for (auto i : g[u]) {
int v = i.to;
int c = i.cost;
if (d[v] > d[u] + c) {
d[v] = d[u] + c;
que.emplace(d[v], v);
}
}
}
// 计算每两个点之间有多少条路径和最短路径长度一致
int *cost = new int[n];
memset(cost, 0, sizeof(int) * n);
for (int u = 0; u
“正是我们每天反复做的事情,最终造就了我们,优秀不是一种行为,而是一种习惯” —亚里士多德
机房租用,北京机房托管,大带宽租用,IDC机房服务器主机租用托管-价格及服务咨询 www.e1idc.net