P1144 最短路计数

这篇具有很好参考价值的文章主要介绍了P1144 最短路计数。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

最短路计数

题目描述

给出一个 N N N 个顶点 M M M 条边的无向无权图,顶点编号为 1 ∼ N 1\sim N 1N。问从顶点 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

样例 #1

样例输入 #1

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

样例输出 #1

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 1245 2 2 2 1 → 3 → 4 → 5 1\to 3\to 4\to 5 1345(由于 4 → 5 4\to 5 45 的边有 2 2 2 条)。

对于 20 % 20\% 20% 的数据, 1 ≤ N ≤ 100 1\le N \le 100 1N100
对于 60 % 60\% 60% 的数据, 1 ≤ N ≤ 1 0 3 1\le N \le 10^3 1N103
对于 100 % 100\% 100% 的数据, 1 ≤ N ≤ 1 0 6 1\le N\le10^6 1N106 1 ≤ M ≤ 2 × 1 0 6 1\le M\le 2\times 10^6 1M2×106

#include<bits/stdc++.h>
using namespace std;
#define il inline
const int MAXN=2e6+5;
const int MOD=100003;
int n,m;
int dis[MAXN],cnt[MAXN];
bool vis[MAXN];
queue<int> q;
vector<int> nextpoints[MAXN];

//bfs
il void bfs()
{
	memset(dis,0x3f3f,sizeof(dis));//初始化
	dis[1]=0;cnt[1]=1;vis[1]=1;
	q.push(1);
	while(!q.empty())//广搜
	{
		int x=q.front();q.pop();
		for(auto y:nextpoints[x])
		{
			
			if(!vis[y])
			{
				if(dis[x]+1<dis[y])
				{
					dis[y]=dis[x]+1;
					vis[y]=true;
					q.push(y);
				}//打标记,存更优
			}
			if(dis[x]+1==dis[y])
			{
				cnt[y]+=cnt[x];
				cnt[y]%=MOD;
			}
		}	
	}
	return;
}
// 

int main()
{
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int u,v;
		cin>>u>>v;
		nextpoints[u].push_back(v);
		nextpoints[v].push_back(u);
	}
	bfs();
	for(int i=1;i<=n;i++)
		cout<<cnt[i]<<endl;//输出答案
	return 0;
} 

ps:

单源最短路问题:
1.可以bfs的同时用cnt记录1~i的最短路径条数
2.假设存在一条 𝑖 → 𝑗 的边。
若 d i s i + 1 < d i s j ,就令 d i s j = d i s i + 1 , c n t j = c n t i ; 若dis_i+1<dis_j,就令dis_j=dis_i+1,cnt_j=cnt_i; disi+1<disj,就令disj=disi+1cntj=cnti
若 d i s i + 1 = d i s j ,就令 c n t j + = c n t i 若dis_i+1=dis_j,就令cnt_j+=cnt_i disi+1=disj,就令cntj+=cnti文章来源地址https://www.toymoban.com/news/detail-623811.html

到了这里,关于P1144 最短路计数的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图论——最短路算法

    如上图,已知图G。 问节点1到节点3的最短距离。 可心算而出为d[1,2]+d[2,3]=1+1=2,比d[1,3]要小。 是一种基于三角形不等式的多源最短路径算法。边权可以为负数 表现为a[i,j]+a[j,k]a[i,k]。 算法思想: 枚举“中转站”(k),“起点”(i),“终点”(j) 设d[i,j]为由i点到j点的最短路径 则  初

    2024年02月13日
    浏览(39)
  • 【图论】最短路算法

    不能处理边权为负的情况, 复杂度O(nlogn) 步骤与基本思路 (1)初始化距离数组dist[N],将其所有值赋为0x3f,并将起点1的dist初始化为0,存入优先队列heap中 (2)从所有 未被遍历 的点中找到与起点1的 距离dist[i]最小 的点,并将该点标记为已遍历 (3)利用刚刚遍历的这个点

    2024年02月16日
    浏览(39)
  • 【图论算法】最短路径算法(无权最短路径、Dijkstra算法、带负边值的图、无圈图)

    本篇博客将考察各种最短路径问题。     无权最短路径     Dijkstra 算法     具有负边值的图     无圈图     所有顶点对间的最短路径     最短路径的例子–词梯游戏 输入是一个赋权图:与每条边 (v i , v j ) 相联系的是穿越该边的开销(或称为值

    2023年04月12日
    浏览(43)
  • 算法——图论——最短路径——Floyd / 传递闭包

    目录  Floyd-Warshall(弗洛伊德)算法 传递闭包 一、试题 算法训练 盾神与离散老师2    求所有顶点到所有顶点的最短路径问题 弗洛伊德算法(Floyd-Warshall algorithm)是一种用于寻找图中所有顶点对之间最短路径的动态规划算法。 该算法可以处理带有负权边但不含负权环的加权

    2024年02月20日
    浏览(41)
  • 图论与算法(7)最短路径问题

    最短路径问题是指在一个加权图中寻找两个顶点之间的最短路径,其中路径的长度由边的权重确定。 常见的最短路径算法包括: Dijkstra算法 :适用于解决单源最短路径问题,即从一个固定的起点到图中所有其他顶点的最短路径。该算法通过不断选择当前路径上权重最小的顶

    2024年02月06日
    浏览(42)
  • 12.图论1 最短路之dijkstra算法

    二分图 判定:染色法。 性质: 可以二着色。 无奇圈。 树的直径模板 两遍dfs/bfs,证明时反证法的核心是用假设推出矛盾。 设1是一开始随机选的点,s是与其最远的点,证明s是直径的一端。 反证:假设s不是直径的一端,ss是直径的一端。 现在要做的就是证明ss是直径的一端

    2024年02月20日
    浏览(47)
  • 算法提高-图论-单源最短路的扩展应用

    多源点单终点最短路建图: 创建虚拟源点(创建虚拟源点的时候以是spfa为例 可以在建图的时候建出来,也可以在spfa这直接入队,也是虚拟源点的意思) 反向建图变成单源点多终点,然后遍历终点的dist即可找出最短路 这题挺简单的就不详细说了,主要是第一次遇到计数问题

    2024年02月16日
    浏览(48)
  • 算法提高-图论-单源最短路的综合应用

    多次dijkstra求每个点到其它点的最短距离, 此时相当于建好了一张图,每个点之间的最短距离都知道了,接下来dfs搜一下怎么走最短即可 一篇博客解释了为什么一个正向建图求最小值,反向建图求最大值 根本思想是保证1到n的买卖是连通的

    2024年02月11日
    浏览(75)
  • 图论算法基础:单源最短路径Dijkstra算法分析

    在 有向带权图 中给定一个起始顶点(源点),Dijkstra算法可以求出 所有其他顶点 到源点的最短路径,Dijkstra算法 不能用于同时含有正负权值的边的图 Source 顶点集合:已经确定 到源点的最短路径 的顶点就会加入 Source 集合中, Source 集合初始时只有源点 dist 数组:用于记录每个顶点到

    2024年02月11日
    浏览(44)
  • 图论与算法(遍历、最小生成树、最短路径)

    图是由顶点集合及顶点间的关系组成的一种数据结构:G = (V, E),其中:顶点集合V = {x|x属于某个数据对象集}是有穷非空集合;E = {(x,y)|x,y属于V}或者E = {x, y|x,y属于V Path(x, y)}是顶点间关系的有穷集合,也叫做边的集合。(x, y)表示x到y的一条双向通路,即(x, y)是无方向的;Path

    2024年04月14日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包