P1144 最短路计数 题解

本文主要是介绍P1144 最短路计数 题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

给出一个 $N$ 个顶点 $M$ 条边的无向无权图，顶点编号为 $1\sim N$。问从顶点 $1$ 开始，到其他每个点的最短路有几条。

输入格式

第一行包含 $2$ 个正整数 $N,M$，为图的顶点数与边数。

接下来 $M$ 行，每行 $2$ 个正整数 $x,y$，表示有一条由顶点 $x$ 连向顶点 $y$ 的边，请注意可能有自环与重边。

输出格式

共 $N$ 行，每行一个非负整数，第 $i$ 行输出从顶点 $1$ 到顶点 $i$ 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 $i$ 则输出 $0$。

样例

样例输入

5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5

样例输出

1
1
1
2
4

数据范围与提示

样例说明：$1$ 到 $5$ 的最短路有 $4$ 条，分别为 $2$ 条 $1\to 2\to 4\to 5$ 和 $2$ 条 $1\to 3\to 4\to 5$（由于 $4\to 5$ 的边有 $2$ 条）。

对于 $20\%$ 的数据，$1\le N\le 100$；
对于 $60\%$ 的数据，$1\le N\le 10^3$；
对于 $100\%$ 的数据，$1\le N\le 10^6$，$1\le M\le 2\times 10^6$。

题目传送门

完整代码

#include <bits/stdc++.h>
using namespace std;
inline int read() {register int x = 1, ans = 0;register char ch = getchar();while (ch < '0' || ch > '9') {if (ch == '-')x = -1;ch = getchar();}while (ch >= '0' && ch <= '9') {ans = (ans << 3) + (ans << 1) + ch - 48;ch = getchar();}return x * ans;
}
int n, m, c = 0;
bool vis[1000002];
int h[4000002], dist[1000002], cnt[1000002];
struct node {int to, nxt;
} e[4000002];
void add(int u, int v) {e[++c].to = v;e[c].nxt = h[u];h[u] = c;
}
struct cmp {bool operator()(int a, int b) { return dist[a] > dist[b]; }
};
priority_queue<pair<int, int> > q;
int main() {n = read(), m = read();for (int i = 1, a, b; i <= m; i++) {a = read(), b = read();add(a, b), add(b, a);}memset(dist, 0x3f, sizeof(dist));dist[1] = 0, cnt[1] = 1;q.push(make_pair(0, 1));while (q.size()) {int u = q.top().second;q.pop();if (vis[u])continue;vis[u] = 1;for (int i = h[u]; i; i = e[i].nxt) {int v = e[i].to;if (dist[v] > dist[u] + 1) {dist[v] = dist[u] + 1, cnt[v] = cnt[u];q.push(make_pair(-dist[v], v));} else if (dist[v] == dist[u] + 1)cnt[v] = (cnt[v] + cnt[u]) % 100003;}}for (int i = 1; i <= n; i++)printf("%d\n", cnt[i]);return 0;
}

这篇关于P1144 最短路计数 题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---