我是靠谱客的博主 平淡鞋垫,这篇文章主要介绍【最短路】洛谷P1144 最短路计数(注意过程取模问题),现在分享给大家,希望可以做个参考。

题目

LP1144

思路

正常最短路,检测到可以松弛覆盖最短路个数,检测到路径相等最短路个数加上即可。
本题注意过程取模问题,程序过程中就要及时取模,不要到了输出的时候再,不然鬼知道会不会爆。

代码

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <cstdio> #include <cstdlib> #include <cstring> #include <algorithm> #include <iostream> #include <vector> #include <queue> #define _for(i,a,b) for(int i = a; i<b; i++) #define _rep(i,a,b) for(int i = a; i<=b; i++) using namespace std; const int INF = 2000000 + 1000; const int maxn = 1000000 + 10; const int MOD = 100003; int n, m, d[maxn], c[maxn]; bool done[maxn]; vector<int> G[maxn]; struct HeapNode { int u, d; bool operator < (const struct HeapNode& rhs) const { return d>rhs.d; } HeapNode(int u, int d) :u(u), d(d) {}; }; void dijkstra(int s) { priority_queue<HeapNode> q; HeapNode first(s, 0); q.push(first); _rep(i, 1, n) d[i] = INF; d[s] = 0; c[s] = 1; while (!q.empty()) { HeapNode now = q.top(); q.pop(); int u = now.u; if (done[u]) continue; done[u] = true; _for(i, 0, G[u].size()) { int v = G[u][i]; if (!done[v] && d[u] + 1 <= d[v]) { if (d[u] + 1 < d[v]) { d[v] = d[u] + 1; c[v] = c[u]; HeapNode nn(v, d[v]); q.push(nn); } else { c[v] += c[u]; c[v] %= MOD; } } } } } int main() { scanf("%d%d", &n, &m); int u, v; _for(i, 0, m) { scanf("%d%d", &u, &v); if (u == v) continue; G[u].push_back(v); G[v].push_back(u); } dijkstra(1); _rep(i, 1, n) printf("%dn", c[i]); return 0; }

最后

以上就是平淡鞋垫最近收集整理的关于【最短路】洛谷P1144 最短路计数(注意过程取模问题)的全部内容,更多相关【最短路】洛谷P1144内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(89)

评论列表共有 0 条评论

立即
投稿
返回
顶部