首页 > 其他分享 >那一天她离我而去 (二进制分组建图)

那一天她离我而去 (二进制分组建图)

时间:2024-08-13 14:49:19浏览次数:8  
标签:ch vis 二进制 一天 int while 组建 read dis

首先比较好想的是断边跑dij,虽然能过(数据太水),但是可以被菊花图给卡掉。

那我们就考虑怎样可以降低复杂度,图论唯一能优化的应该就是建图了吧。

这里我们就可以进行分组最短路,通过二进制来确保分组的正确性,因为任意两个不同的点,二进制一定至少存在一位不同。于是我们以每个二进制位的0,1进行分组,每组点组成的环至少被更新一次。

点击查看代码
#include<bits/stdc++.h>
using namespace std;

const int N=5e5+107;
int n,m,e,f;


int read()
{
	int f=1,s=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){s=(s<<1)+(s<<3)+(ch^48);ch=getchar();}
	return f*s;
}


int h[N<<1],to[N],nxt[N],w[N],tot;
void add(int x,int y,int dt)
{
	to[++tot]=y;
	nxt[tot]=h[x];
	w[tot]=dt;
	h[x]=tot;
}

priority_queue<pair<int,int>>q;
bool vis[N];
int dis[N];
void dij(int x)
{
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	dis[x]=0;
	q.push(make_pair(-dis[x],x));
	while(!q.empty())
	{
		// cout<<"!!";
		x=q.top().second;
		q.pop();
		if(x==f) return ;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=h[x];i;i=nxt[i])
		{
			int y=to[i];
			// vis[y]=1;
			if(dis[y]>dis[x]+w[i])
			{
				dis[y]=dis[x]+w[i];
				if(!vis[y])
				{
					q.push(make_pair(-dis[y],y));
				}
			}
		}
	}
}

int cnt;
struct lmy
{
	int y,w;
}c[N];

void clear()
{
	memset(h,0,sizeof h);
	tot=2; cnt=0;
}



int main()
{
	// freopen("in.in","r",stdin);
	// freopen("out.out","w",stdout);

	int T=read();
	while(T--)
	{
		clear();
		int ans=0x3f3f3f3f;
		n=read(),m=read();
		for(int i=1;i<=m;i++)
		{
			int x=read(),y=read(),dt=read();
			if(x>y) swap(x,y);
			if(x==1) c[++cnt]={y,dt};
			else add(x,y,dt),add(y,x,dt);

		}
		int z=n;
		for(int i=1;i<=n;i<<=1)
		{
			e=++z,f=++z;
			for(int j=1;j<=cnt;j++)
			{
				if(c[j].y&i) add(e,c[j].y,c[j].w);
				else add(c[j].y,f,c[j].w);
			}
			dij(e);
			ans=min(ans,dis[f]);
		}
		if(ans==0x3f3f3f3f) ans=-1;
		printf("%d\n",ans);

	}
	return 0;
}

标签:ch,vis,二进制,一天,int,while,组建,read,dis
From: https://www.cnblogs.com/zhengchenxi/p/18356130

相关文章

  • 算法的学习笔记——二进制中 1 的个数(牛客JZ15)
    ......
  • 前端二进制文件转blob链接
    背景有的时候后端返回文件,文件是属于stream类型(二进制格式),我们获取到二进制格式的文件后可能是需要下载,也直接在页面上预览等等。代码<template><divclass="app"><iframe:src="iframeSrc"scrolling="auto"style="border:0;height:100vh;wid......
  • 实习第一天,不小心透露了,我是拆迁户
    2018年6月,大三暑假进行时上班之前,我提前跟家里人打过招呼了。我说我已经拿到了实习的offer,明天就过去上班,离家里很近,月薪3500,我骑自行车过去就行。家里人就说挺好的,让我骑个电瓶车,这样会快点,嘱咐我好好干。这是我第一次正式上班,我还觉得挺神奇的,没想到我都要上班了。大学以前......
  • HBase学习的第一天--hbase的简介和搭建
    HBase架构与基础命令一、了解HBase1.1 HBase概述HBase是基于Hadoop中HDFS做存储的数据库HBase是一个高可靠性、高性能、面向列、可伸缩的分布式存储系统,用于存储海量的结构化或者半结构化,非结构化的数据(底层是字节数组做存储的)HBase是Hadoop的生态系统之一,是建立在Hadoop......
  • 记录兼职运维的一天
    1.背景7月底部门的运维大哥离职了,奈何又没有新运维接替,至于为什么没有补位,懂得都懂,按老大的意思是先让开发一人顶一块,8月底争取补上。打心底我有点排斥这事,但是人到中年又有什么办法呢,上有老下有小,唯有苟。分派给我的部分是服务器漏洞的修复,小弟虽然懂几个linux命令但是在“漏......
  • Kubernetes-二进制高可用部署v1.23.x
    目录高可用架构k8s集群组件ectdkube-apiserverkube-schedulerkube-controller-managerkubeletkube-proxykubectl高可用分析负载均衡节点设计1.环境准备1.1环境规划1.2所有节点配置host解析1.3安装必备工具1.4所有节点关闭防火墙、selinux、dnsmasq、swap1.5Master01节点免密......
  • Prometheus系列二进制部署
    Prometheus二进制部署官网下载prometheusDownload|Prometheus解压压缩包tar-zxvfprometheus-2.54.0.linux-amd64.tar.gz移动到安装路径下mv./prometheus-2.54.0.linux-amd64/usr/local/bin/prometheus创建启动用户(可选)sudouseradd-rs/bin/falseprometheu......
  • Linux:@2024-08-11 最新的Openssl-3.3.1 Openssh-9.8p1 Centos7上的编译后二进制 一键
     附件:Portable_Openssl-Openssh9.8p1-bin-el7.v1.4.1.tgz.zip 特点:适用于centos7.x 已经编译为二进制对老版本的关键二进制文件sshd、sftp、scp、openssl进行了备份升级前,自动打开一个端口为2222的老版本的sshd服务,你可以连接那个2222的服务,以防死翘翘。对sshd_confi......
  • Leetcode-3129 找出所有稳定的二进制数组I
    Leetcode-3129找出所有稳定的二进制数组I1.题目描述2.解题思路3.代码实现1.题目描述3129找出所有稳定的二进制数组I2.解题思路(1)定义f[i][j][k]表示i个0、j个1且当前位i+j填写值为k=0/1的所有情况;(2)对于f[i][0][0]、f[0][j][1]初始化为1,注意到:......
  • 操作符详解(内含二进制与原、反、补码知识点)--还有超详细图解!一看就会!
    前言今天给大家分享一下C语言操作符的详解,但在此之前先铺垫一下二进制和进制转换与原码、反码、补码的知识点,都有详细的图解,也希望这篇文章能对大家有所帮助,大家多多支持呀!目录前言一、二进制和进制转换1.  10进制转化为10进制​2.  2进制转化为10进制 ​2.......