深圳网站建设公司怎么样,网页设计与制作个人网站,东莞企业型网站建设,大丰做网站需要多少钱题目
给出一个 N 个顶点 M 条边的无向无权图#xff0c;顶点编号为 1 到 N。
问从顶点 1 开始#xff0c;到其他每个点的最短路有几条。
输入格式
第一行包含 2 个正整数 N,M#xff0c;为图的顶点数与边数。
接下来 M 行#xff0c;每行两个正整数 x,y#xff0c;表…题目
给出一个 N 个顶点 M 条边的无向无权图顶点编号为 1 到 N。
问从顶点 1 开始到其他每个点的最短路有几条。
输入格式
第一行包含 2 个正整数 N,M为图的顶点数与边数。
接下来 M 行每行两个正整数 x,y表示有一条顶点 x 连向顶点 y 的边请注意可能有自环与重边。
输出格式
输出 N 行每行一个非负整数第 i 行输出从顶点 1 到顶点 i 有多少条不同的最短路由于答案有可能会很大你只需要输出对 100003 取模后的结果即可。
如果无法到达顶点 i 则输出 0。
数据范围
1≤N≤1e5 1≤M≤2e5
输入样例
5 7
1 2
1 3
2 4
3 4
2 3
4 5
4 5输出样例
1
1
1
2
4
思路 变量介绍 从点1出发开始搜索设每条边的长度为1。 如果从点 t 到达点 u 时所走的路径长度小于dist[ u ]则进行 将点 u 的cnt[ u ] 更新为cnt[ t ]dist[ u ] 更新为 dist[ t ] 1。 如果从点 t 到达点 u 时所走的路径长度等于 dist[ u ]则进行 将cnt[t] 加到 cnt[u] 上面。 如果从点 t 到达点 u 时所走的路径长度大于 dist[ u ]则不进行任何操作。
代码
#includebits/stdc.h
using namespace std;
const int N 100100, M 4 * N;
int n,m;
int h[N],ne[M],e[M],idx;
int dist[N],cnt[N];
bool st[N];void add(int a,int b)
{ne[idx] h[a],e[idx] b,h[a] idx ;
}void bfs()
{memset(dist,0x3f,sizeof dist);queueint q;cnt[1] 1;dist[1] 0;q.push(1);st[1] true;while(!q.empty()){int t q.front();st[t] false;q.pop();for(int i h[t]; ~i; i ne[i]){int u e[i];if(dist[u] dist[t] 1){dist[u] dist[t] 1;cnt[u] cnt[t];cnt[u] % 100003;if(!st[u]) q.push(u);}else if(dist[u] dist[t] 1){cnt[u] cnt[t];cnt[u] % 100003;}}}
}int main()
{cin n m;memset(h,-1,sizeof h);while(m --){int a,b;cin a b;add(a,b);add(b,a);}bfs();for(int i 1; i n; i ) printf(%d\n,cnt[i]);return 0;
}
难度中等时/空限制1s / 64MB总通过数6250总尝试数11237来源《信息学奥赛一本通》算法标签 最短路 方案数
题目来自 1134. 最短路计数 - AcWing题库
