吉林3厅官齐聚任免大会宁波网站建设,手机网站建设yu,网站制作维护,微信小程序怎么做活动文章目录 题目描述输入格式输出格式样例样例输入样例输出 数据范围与提示完整代码 题目描述
给出一个 N N N 个顶点 M M M 条边的无向无权图#xff0c;顶点编号为 1 ∼ N 1\sim N 1∼N。问从顶点 1 1 1 开始#xff0c;到其他每个点的最短路有几条。
输入格式
第一行… 文章目录 题目描述输入格式输出格式样例样例输入样例输出 数据范围与提示完整代码 题目描述
给出一个 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。
题目传送门
完整代码
#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_queuepairint, 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;
}
