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

题目描述

她走的悄无声息，消失的无影无踪。

至今我还记得那一段时间，我们一起旅游，一起游遍山水。到了最
终的景点，她却悄无声息地消失了，只剩我孤身而返。

现在我还记得，那个旅游区可以表示为一张由(n)个节点(m)条边组成无向图。

我故地重游，却发现自己只想尽快地结束这次旅游。我从景区的出发点（即 (1) 号节点）出发，却只想找出最短的一条回路重新回到出发点，并且中途不重复经过任意一条边。
即：我想找出从出发点到出发点的小环。

输入格式

每个测试点有多组测试数据
第一行有一个正整数(T,(T leq 10))
表示数据组数
接下来对于每组数据，第一行有两个正整数(n,m,(n leq 10 ^4,m leq 4 imes 10^4)) 分别代表图的点数和边数
接下来有(m)行，每行三个整数 (u,v,d)表示(u,v)之间存在一条长度为(d,(d leq 10^3))的路径
保证不存在重边，自环。

输出格式

对于每组测试数据，输出题目中所求的最小环的长度。
无解输出 (-1)

样例

样例输入

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

样例输出

3
8

数据范围与提示

对于(30\%)的数据,(n leq 10^3,mleq 4 imes 10^3)
对于另外(30\%)的数据,(n leq 10^4,m=n)
对于(100\%)的数据,(n leq 10^4,mleq 5 imes 10^4)

分析

一个暴力的思路是，将所有与起点相连的边删除，从这些相连的点跑到其他相连点的最短路尝试更新答案。
可以尝试优化这个暴力思路。
发现这个算法有一部分冗余，我们可以分组进行最短路。
因为任意两个不同的点，二进制一定至少存在一位不同。
我们以每个二进制位的(0),(1)进行分组，每组点组成的环一定被至少一次更新，于是可以达到目的。
复杂度 (O(m log^2n))

代码

#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<cmath>
inline int read(){
	int x=0,fh=1;
	char ch=getchar();
	while(ch<'0' || ch>'9'){
		if(ch=='-') fh=-1;
		ch=getchar();
	}
	while(ch>='0' && ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*fh;
}
const int maxn=2e5+5;
int t,head[maxn],tot=2,n,m,cnt,qd,zd;
struct asd{
	int to,next,val;
}b[maxn];
void ad(int aa,int bb,int cc){
	b[tot].to=bb;
	b[tot].next=head[aa];
	b[tot].val=cc;
	head[aa]=tot++;
}
struct jie{
	int num,jl;
	jie(){}
	jie(int aa,int bb){
		num=aa,jl=bb;
	}
	bool operator < (const jie& A)const{
		return jl>A.jl;
	}
};
bool vis[maxn];
int dis[maxn];
void dij(int qd){
	std::priority_queue<jie> q;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[qd]=0;
	q.push(jie(qd,0));
	while(!q.empty()){
		int now=q.top().num;
		q.pop();
		if(now==zd) return;
		if(vis[now]) continue;
		vis[now]=1;
		for(int i=head[now];i!=-1;i=b[i].next){
			int u=b[i].to;
			if(dis[u]>dis[now]+b[i].val){
				dis[u]=dis[now]+b[i].val;
				q.push(jie(u,dis[u]));
			}
		}
	}
}
struct jl{
	int bh,jz;
	jl(){}
	jl(int aa,int bb){
		bh=aa,jz=bb;
	}
}c[maxn];
int main(){
	freopen("leave.in","r",stdin);
	freopen("leave.out","w",stdout);
	t=read();
	while(t--){
		memset(head,-1,sizeof(head));
		memset(&b,0,sizeof(b));
		memset(&c,0,sizeof(c));
		tot=2,cnt=0;
		n=read(),m=read();
		for(int i=1;i<=m;i++){
			int aa,bb,cc;
			aa=read(),bb=read(),cc=read();
			if(aa>bb) std::swap(aa,bb);
			if(aa==1) c[++cnt]=jl(bb,cc);
			else {
				ad(aa,bb,cc);
				ad(bb,aa,cc);
			}
		}
		int nans=0x3f3f3f3f,nn=n;
		for(int i=1;i<=n;i<<=1){
			qd=++nn,zd=++nn;
			for(int j=1;j<=cnt;j++){
				if(c[j].bh&i) ad(qd,c[j].bh,c[j].jz);
				else ad(c[j].bh,zd,c[j].jz);
			}
			dij(qd);
			nans=std::min(nans,dis[zd]);
		}
		if(nans==0x3f3f3f3f) printf("-1
");
		else printf("%d
",nans);
	}
	return 0;
}