首页 > 编程语言 >codeforces round 974(div.3)E(优先队列实现dijstra算法,devc++的优先队列用greater报错)

codeforces round 974(div.3)E(优先队列实现dijstra算法,devc++的优先队列用greater报错)

时间:2024-10-09 22:11:51浏览次数:11  
标签:优先 pq greater 队列 dijstra int 报错

解题历程:

看到两边同时移动,计算最终的相遇时间,我就想到两边同时计算各点到起点的最短距离,就是使用dijstra算法,最后所有节点取两次计算的最大值,再对所有节点取最小值,就是最终答案了,可是这个思路没有考虑有马的情况,思考一番后发现可以多列一个数组记录有马的情况下的行走最短路,然后将有马和无马取最小值合并成单源最短路的结果

代码:

#include<bits/stdc++.h>
 
#define ll long long
 
#define inf 1e18
using namespace std;
 
void solve() {
    int n,m,h;
    cin>>n>>m>>h;
    vector<vector<pair<ll,ll>>>a(n+1);
    vector<int>horse(n+1,0);
    for(int i=0;i<h;i++)
    {
    	int l;
    	cin>>l;
    	horse[l]=1;
	}
    for(int i=1;i<=m;i++)
    {
    	ll u,v,w;
    	cin>>u>>v>>w;
    	a[u].push_back({v,w});
    	a[v].push_back({u,w});
	}
	
	auto dijstra=[&](int s){
		priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<>>pq;//devc++要用greater<ll>
		vector<ll>vis(2*n+5,inf);
		pq.push({0ll,2*s});
		while(!pq.empty()){
			ll d=pq.top().first;
			ll u=pq.top().second;
			pq.pop();
			if(vis[u]!=inf)continue;
			vis[u]=d;
			int x=u%2;
			int y=(u+1)/2; 
			if(x==0&&horse[y])
			{
				pq.push({d,y*2-1});
			}
			for(auto t:a[y])
			{
				pq.push({d+t.second/(1+x),2*t.first-x});
			}
			
		
		}
		vector<ll>d(n+1,inf);
		for(int i=1;i<n+1;i++)
		{
			d[i]=min(vis[i*2],vis[2*i-1]);
		}
		return d;
	};
    auto dl=dijstra(1);
    auto dr=dijstra(n);
	ll ans=inf;
	for(int i=0;i<n;i++)
	{
		ans=min(ans,max(dl[i+1],dr[i+1]));
	}
	if(ans!=inf)
	cout<<ans<<endl;
	else
	cout<<-1<<endl;
}
 
int main(void )
{   
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
    int test=1;
    cin>>test;
    while(test--)
    {
    	solve();
	}
        
    return 0;
}
 

感悟:

  1. 以后卡题了可以考虑多开数组记录数据,算法竞赛不用省空间

  2. 优先队列的dijstra算法要实现的话只需要一个优先队列,一个数组,优先队列用pair容器,pair用于存储该点的编号和该点到起点的距离,数组起始都是inf,用于记录对应编号的点到起点的最短距离。首先将起点和距离0装入队列。然后循环以下操作:将队首出队,队首是队列中离起点最近的点,判断该点是否已经赋值过,若是没有被赋值过,则将该距离赋给该点,否则就不赋值跳过后面的操作,赋值后将该点相关联的点和父点的离起点的距离加上父点到该点的距离一起存入队列。循环以队列为空时停止,此时数组的数值就是对应点到起点的最短路径了。

  3. dijstra算法的思想和dp非常的像,都是将局部的最优解存起来,在后面的步骤可以直接用,这样可以省去重复的计算

  4. devc++有一个坑点,优先队列中的greater<>中尖括号内需要加上变量类型,比如greater< int >,不然的话会报错,有些编译器不加也能运行

标签:优先,pq,greater,队列,dijstra,int,报错
From: https://www.cnblogs.com/cavendishboys/p/18455285

相关文章

  • C#使用线程安全队列ConcurrentQueue处理数据
    usingSystem;usingSystem.Collections.Concurrent;usingSystem.Collections.Generic;usingSystem.Globalization;usingSystem.Linq;usingSystem.Text;usingSystem.Threading;usingSystem.Threading.Tasks;namespaceConsoleApp10{internalclassProg......
  • Vscode中的行尾序列CRLF/LF问题,及其引起的Delete ‘␍‘ 的报错问题
    本人使用的是Windows系统,Unix/Linux/macOS系统也可参照此方法解决问题报错如图:(如果你只想解决报错的话直接下翻到解决方法,想了解原理的话请耐心看完)在这之前,我们先来了解一下什么是行尾符(也叫换行符/行尾序列)。行尾符是用于标记文本文件中一行结束的字符,不同的操作系统使......
  • 运行CtsVerifier.apk报错
    要过GMS认证,遇到个问题。安装CtsVerifier.apk。前面几个选项都OK。可以测试成功。执行CameraITSTest的时候崩溃。查看log:r:AccessinghiddenmethodLandroid/hardware/devicestate/DeviceStateManager;->getSupportedStates()[I(blocked,test-api,linking,denied......
  • 停止训练后报错torch.cuda.OutOfMemoryError: CUDA out of memory. 及查看进程和停止
    停止训练后遇到 torch.cuda.OutOfMemoryError 错误,意味着你的GPU内存不足,无法分配更多内存给当前的PyTorch操作。查看进程并关闭相关进程就可恢复。在不同的操作系统中,查看进程的方法有所不同。以下是常见操作系统的命令:在Linux和macOS系统中,你可以使用以下几种方法来......
  • 调用sdapi/v1/txt2img接口,报错“Couldn‘t load custom C++ ops”
    后端启动stable_diffusion的api接口nohuppythonlaunch.py --use-cpuall--skip-torch-cuda-test   --api--api-log  --listen--server-name192.168.1.204>/home/third_party_app/llm/stable-diffusion-webui/logs/all.log2>&1 &服务接口http://192.168......
  • 【堆】【优先队列】[NOIP2004]合并果子
    https://ac.nowcoder.com/acm/contest/22669/I堆的用法Type:队列中存储元素的类型。例如int,double,pair<int,int>等。Container:底层存储数据的容器类型,默认为vector,但可以换成deque或其他容器。Compare:比较函数,用于决定优先级顺序。默认是less,表示最大堆。如果使用......
  • nacos gateway 调用服务报错503 Server unavailable
    环境springboot3jdk17依赖<dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-bootstrap</artifactId></dependency><dependency><groupId>org.springframe......
  • springboot-网站开发-thymeleaf引擎报错找不到指定的页面模板文件
    springboot-网站开发-thymeleaf引擎报错找不到指定的页面模板文件!这种错误的情况,发生,一般都是因为,我们自己的html模板文件,存档位置并不是在默认的templates下面。而是我们自己新建的一个子目录里面。然后,我们在java代码里面,控制器方法体内,return,返回模板的时候,我们多写了一个......
  • 单调栈/单调队列
    1.单调栈给定一个长度为\(n\)的数列\(a\),对每个数字求出其右/左边第一个值大于等于它的数字的位置。考虑从左到右扫整个序列,维护一个栈,里面存放可能成为答案的数字,当遍历到一个新的数\(a_i\)的时候,可以发现栈中\(\leqa_i\)的数就再也不可能成为答案了,那就把它们弹掉,......
  • C# WebService返回参数为DataTable报错“XML文档有错误”
    该问题由于DataTable列存在自定义类型。解决该报错需要以下几步:1、自定义类型增加xml序列化2、由于C#从XML反序列化DataSet或DataTable时的默认限制,所以需要先把调用方的项目开放限制,如果是.netframework项目,需要在app.config中添加<configuration><runtime>......