首页 / C++ / 最短路计数- C++
最短路计数- C++
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了最短路计数- C++，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1670字，纯文字阅读大概需要3分钟。
内容图文
最短路计数
题目描述 给出一个 N 个顶点 M 条边的无向无权图，顶点编号为1?N。问从顶点1开始，到其他每个点的最短路有几条。
输入格式 第一行包含2个正整数N,M，为图的顶点数与边数。
接下来M行，每行2个正整数x,y，表示有一条顶点 x 连向顶点 y 的边，请注意可能有自环与重边。
输出格式 共N行，每行一个非负整数，第 i 行输出从顶点1到顶点 i 有多少条不同的最短路，由于答案有可能会很大，你只需要输出 ans? mod ?100003 后的结果即可。如果无法到达顶点 i 则输出 0 。
输入输出样例 输入 #1
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5
输出 #1
1
1
1
2
4
这题就是得注意起点是1，而如果在未遍历该节点时，此时该节点的路径就是等于它前一个节点路径。若已经遍历过该节点，则此时节点路径便要加上上一个节点的路径。
C++代码：
#include<iostream>
#include<cstdio>
#include<queue>
#define maxPath 999999999
using namespace std;
int dis[1000001],cnt;
int book[1000001];
int ans[1000001];
int head[1000001];
queue <int> q;
struct edge{
int v;
int next;
};
edge e[2000001];
void add(int u, int v)
{
cnt ++;
e[cnt].v = v;
e[cnt].next = head[u];
head[u] = cnt;
}
int main()
{
int N,M;
cin >> N >> M;
for(int i = 1; i <= N; i ++)
dis[i] = maxPath;
dis[1] = 0;
for(int i = 1; i <= M; i ++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
add(v,u);
}
q.push(1);
book[1] = 1;
ans[1] = 1;
int k = 0;
while(q.size())
{
k = q.front();
q.pop();
for(int i = head[k]; i != 0; i = e[i].next)
{
if(dis[e[i].v] > dis[k] + 1)
{
dis[e[i].v] = dis[k] + 1;
ans[e[i].v] = ans[k];
//判断改点是否入了队列
if(book[e[i].v] == 0)
{
q.push(e[i].v);
book[e[i].v] = 1;
}
}else
if(dis[e[i].v] == dis[k] + 1)
{
ans[e[i].v] += ans[k];
ans[e[i].v] %= 100003;
}
}
}
for(int i = 1; i <= N; i ++)
cout << ans[i] << endl;
return 0;
}
内容总结
以上是互联网集市为您收集整理的最短路计数- C++全部内容，希望文章能够帮你解决最短路计数- C++所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。