题目描述
给出一个 N N N 个顶点 M M M 条边的无向无权图，顶点编号为 1 ∼ N 1\sim N 1∼N。问从顶点 1 1 1 开始，到其他每个点的最短路有几条。
输入格式
第一行包含 2 2 2 个正整数 N , M N,M N,M，为图的顶点数与边数。
接下来 M M M 行，每行 2 2 2 个正整数 x , y x,y x,y，表示有一条由顶点 x x x 连向顶点 y y y 的边，请注意可能有自环与重边。
输出格式
共 N N N 行，每行一个非负整数，第 i i i 行输出从顶点 1 1 1 到顶点 i i i 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 $ ans \bmod 100003$ 后的结果即可。如果无法到达顶点 i i i 则输出 0 0 0。
样例
样例输入
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
样例输出
1
1
1
2
4
数据范围与提示
样例说明： 1 1 1 到 5 5 5 的最短路有 4 4 4 条，分别为 2 2 2 条 1 → 2 → 4 → 5 1\to 2\to 4\to 5 1→2→4→5 和 2 2 2 条 1 → 3 → 4 → 5 1\to 3\to 4\to 5 1→3→4→5（由于 4 → 5 4\to 5 4→5 的边有 2 2 2 条）。
对于
20
%
20\%
20% 的数据，
1
≤
N
≤
100
1\le N \le 100
1≤N≤100；
对于
60
%
60\%
60% 的数据，
1
≤
N
≤
1
0
3
1\le N \le 10^3
1≤N≤103；
对于
100
%
100\%
100% 的数据，
1
≤
N
≤
1
0
6
1\le N\le10^6
1≤N≤106，
1
≤
M
≤
2
×
1
0
6
1\le M\le 2\times 10^6
1≤M≤2×106。文章来源：https://www.toymoban.com/news/detail-745175.html
题目传送门文章来源地址https://www.toymoban.com/news/detail-745175.html
完整代码
#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 最短路计数 题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
