本题为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 号房间的路径长度，对于所有满足 \(1\leq i\leq 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% 的数据，\(2\leq N\leq 5\) ，\(M\leq 10\) 。
对于 50% 的数据，满足条件的方案数不超过 10000。
对于 100% 的数据，\(2\leq N\leq 1000\)，\(N – 1\leq M\leq \frac{N\times (N – 1)}{2}\)，\(1 \leq L\leq 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 <bits/stdc++.h>
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<vector<edge>> g(n, vector<edge>()); // 邻接表
// 输入各个边,构建邻接表
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模板
priority_queue<pair<int, int>> 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 < n; u++) {
for (auto i : g[u]) {
int v = i.to;
int c = i.cost;
if (d[v] - d[u] == c) { // 如果当前两点间的最短路径和当前两点之间的边长相等,证明有多种选择
cost[v]++;
}
}
}
// 利用分步乘法计数原理计算出最短路径树的数量
i64 res = 1;
for (int i = 0; i < n; i++) {
if (cost[i]) {
res = res * cost[i] % ((1LL << 31) - 1); // (1LL << 31) - 1即为2^31 - 1,LL表示这个字面量1是long long类型而不是默认的int类型
}
}
cout << res << "\n";
delete[] d;
delete[] cost;
return 0;
}
标签：int,城堡,路径,最短,leq,cost,lsp From： https://www.cnblogs.com/geministar/p/zstu23_3_17_B.html"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德