首页 > 其他分享 >【技巧】0/1最短路

【技巧】0/1最短路

时间:2024-07-24 15:20:31浏览次数:14  
标签:技巧 int 短路 front que way push

这是 $Dijkstra$。
void dijkstra(int x)
{
	priority_queue<pair<int,int>>que;
	memset(d,0x3f,sizeof(d));
	d[x]=0;
	que.push({-d[x],x});
	while(!que.empty())
	{
		int y=que.top().second;
		que.pop();
		e[y]=true;
		for(ri i=f[y];i;i=way[i].h)
		{
			int z=way[i].to; 
			if(d[z]>d[y]+way[i].quan)
			{
				d[z]=d[y]+way[i].quan;
				if(!e[z])
				{
					que.push({-d[z],z});
				}
			}
		}
	}
}

时间复杂度 \(O(m\log n)\)。

这是SPFA。
void spfa(int x)
{
	queue<int>que;
	memset(d,0x3f,sizeof(d));
	d[x]=0;
	que.push(x);
	e[x]=true;
	while(!que.empty())
	{
		int y=que.front();
		que.pop();
		e[y]=false;
		for(int i=f[y];i;i=way[i].h)
		{
			z=way[i].to;
			if(d[z]<d[y]+way[i].quan)
			{
				d[z]=d[y]+way[i].quan;
				if(!e[z])
				{
					way.push(z);
					e[z]=true;
				}
			}
		}
	}
}

时间复杂度 \(O(m)\) ~ \(O(nm)\)。

但是,有时我们会遇到边权只有0和1&&数据范围很大的图,这种题的正解往往不是最短路,但是可以拿最短路骗一点分。而0/1最短路的发明,就是为了在这种情况下以更高的效率骗更多的分。
回忆一下 \(Dijkstra\) 为什么比 \(SPFA\) 多个 \(log\),就是因为 \(Dijkstra\) 在维护单调性时使用的优先队列,其内部实现是二叉堆,复杂度 \(O(\log n)\)。但是现在由于只有0/1,故如果想要维护单调性,只需开个双端队列,将0的插到队头,1的插到队尾即可。
代码如下:

il void zerone(int x)
{
	deque<int>que;
	memset(d,0x3f,sizeof(d));
	d[x]=0;
	que.push_front(x);
	while(!que.empty())
	{
		int y=que.front();
		que.pop_front();
		e[y]=true;
		for(ri i=f[y];i;i=way[i].h)
		{
			int z=way[i].to;
			if(e[z])
			{
				continue;
			}
			d[z]=min(d[z],d[y]+way[i].quan);
			if(way[i].quan)
			{
				que.push_back(z);
			}
			else
			{
				que.push_front(z);
			}
		}
	}
}

理论复杂度 \(O(n)\)。
实际上,不只是0/1边权,只要是0和另一正边权的组合都可以如此实现。至于实际应用,自己瞎搞吧。

标签:技巧,int,短路,front,que,way,push
From: https://www.cnblogs.com/ywhhdjser-97/p/18317994

相关文章

  • c++ 《小技巧》
    使用swap回收多余空间#include<vector>#include<iostream>usingnamespacestd;intmain(){vector<int>v;for(inti=0;i<100000;++i){v.push_back(i);}cout<<v.size()<<endl;//100000cout<......
  • 「技巧」对拍
    防挂分的爹7.23模拟赛打完:大黄:这Noi赛制真**,T3先交了次暴力,60pts,后来打了(他自以为的)正解,一分没有,为什么就不能取我最高分算啊ok,对拍的用处就体现出来了:防止我们像大黄一样**。对拍是干什么的对拍就是在防止自己代码打挂或者思路假而自己还不知道,所以自己随数造数据,用......
  • 二分答案解题技巧
    二分答案有一个很显著的特征:一定存在一个临界值,单调性只是临界值的一种,而不是全部。临界值,就是寻找第一个/最后一个满足要求的值,这又分别对应着两个完全不同的二分模板,这里做题时推荐使用“第一个满足要求的值”,即对应着STL中的upper_bound,手写板对应着这篇文章里讲的模板......
  • [技巧] Linux 对拍
    造数据#include<bits/stdc++.h>usingnamespacestd;intrandom(intl,intr){ return(longlong)rand()*rand()%(r-l+1)+l;}intmain(){ freopen("in.in","w",stdout); srand(time(0)); intn=random(2,100000); cout......
  • pytest实战技巧之参数化应用
    pytest是Python中最流行的测试框架之一。它提供了丰富的功能,可以帮助我们编写高效、可靠的测试用例。其中一个重要的功能就是参数化,它可以让我们用不同的数据组合来运行同一个测试用例,从而提高测试覆盖率和效率。本文将介绍pytest参数化的基本用法和一些高级技巧,帮助读者更好地......
  • Johnson 全源最短路算法以及 Primal-Dual 原始对偶算法
    Johnson全源最短路算法引入:多源最短路问题,设点数为\(n\)边数为\(m\)。我们有如下方案:floyd,时间复杂度\(O(n^3)\),适合任意图。Bellman-ford(SPFA),时间复杂度\(O(n^2m)\),适合任意图。Dijkstra,时间复杂度\(O(nm\logm)\),适合非负权图。综上分析,我们发现:Dijkstra的时间......
  • Golang异步编程方式和技巧
    Golang异步编程方式和技巧原创 腾讯程序员 腾讯技术工程  2024年04月23日18:00 广东 12人听过Golang基于多线程、协程实现,与生俱来适合异步编程,当我们遇到那种需要批量处理且耗时的操作时,传统的线性执行就显得吃力,这时就会想到异步并行处理。下面介绍一些异步......
  • docker 容器调试技巧
    有时候docker容器可能因为映射不对,或者内部文件错误等等,会出现一启动就挂掉的情况,这种往往就是容器启动入口的程序有问题,但是因为一启动就挂,有时候日志啥的都看不到。这时候就可以通过command指令去覆盖掉默认Dockerfile里面的CMD定义的入口(EntryPoint定义的也类似)。覆......
  • C# 开发技巧 轻松监控方法执行耗时
    前言MethodTimer.Fody是一个功能强大的库,可以用于测量.NET应用程序中的方法的执行时间。允许你在不修改代码的情况下,自动地测量和记录方法的执行时间。这个工具是基于.NET的weaving技术,通过修改IL(IntermediateLanguage,中间语言)代码来插入计时逻辑,从而在方法调用前后记录时......
  • 获取所有钥匙的最短路径
    获取所有钥匙的最短路径-力扣(LeetCode)听完左程云teacher的讲解感觉这道题很简单不就是记录一下我有几把钥匙走到这个点我有几把钥匙夺走几次和普通bfs一样只是我要多走几次,等到上手发现真的难,水平还是太差了,开始我需要进行初始化每一个的初始化,不然我有问题,他的核心代码很......