P4366 [Code+#4]最短路

首先，可以证明，不存在一种最短路算法的时间复杂度与边数无关

其次，我们发现，这里的代价是与异或有关的，

异或可以被认为是将不同的二进制位变为相同，所以我们可以发现，两个点直接连边的代价就是将两个点变为一样的代价

举个例子

这张图片中，我们发现，异或中，若两个二进制位相同，我们不需要支付代价

这里我们就有了一个想法，我们将每一位改变的代价分别算出来，就能将一个数转移到另一个数上去

就像这样，我们可以通过对原数每一位的变动，使其到达另一个数上，从而实现转移

于是就可以愉快的敲代码了

注意一下，这里的节点数上界是n*2，数组要开两倍

用的是 zkw 线段树优化的 Dijkstra

#include <vector>
#define pii pair<int,int>
#include <stdio.h>
#include <bitset>
#include <string.h>

using namespace std;
const int maxN=2*1e5+10;
const int inf=0x7ffffff;
int N=1,n,m,c,s,t,dis[maxN];
vector<pii> g[maxN];
bitset<maxN> vis;

struct node {
	int minx[maxN<<2],mind[maxN<<2];
	void pushup(int x){
		mind[x]=(minx[x<<1]<minx[(x<<1)|1])?mind[x<<1]:mind[(x<<1)|1];
		minx[x]=min(minx[x<<1],minx[(x<<1)|1]);
	}
	void build(){
		for(int i=0;i<n;++i) mind[i+N]=i+N,minx[i+N]=inf;
		for(int i=N-1;i>=1;--i) pushup(i);
	}
	void add(int x,int v){
		minx[x+N-1]=v;
		for(int i=(N+x-1)>>1;i;i>>=1) pushup(i);
	}
	int mid(){
		return mind[1]-N+1;
	}
}tree; 

void dijkstra(){
	tree.build();
	tree.add(s,0);
//	cout << N << endl;
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
//	cout << tree.mid() << endl;
//	cout << tree.minx[7] << endl;
//	tree.add(3,-inf);
//	cout << tree.mid() << endl;
//	cout << tree.minx[6] << endl;
	while(tree.minx[1]!=inf){
		int temp=tree.mid();
	//	cout << temp << endl;
		tree.add(temp,inf);
		if(vis[temp]) continue ;
		vis[temp]=1;
		for(pii x:g[temp]){
			if(dis[x.first]>dis[temp]+x.second){
				dis[x.first]=dis[temp]+x.second;
				//cout <<"dis:" <<dis[x.first] << endl;
				tree.add(x.first,dis[x.first]); 
			}
		}
	}
}


int main(){
	//cin >> n >> m >> c;
	scanf("%d%d%d",&n,&m,&c);
	
	int x,y,z;
	for(int i=1;i<=m;++i)
		scanf("%d%d%d",&x,&y,&z),g[x].push_back({y,z});
	scanf("%d%d",&s,&t);	
	//cout << s << " " << t << endl;
	for(int i=0;i<=n*2;++i){
		//这里用2^k来异或一个数，本质上就是对这个数的二进制的某一位进行 添1/去1 的操作
		//异或的过程实际上可以被认为是将两个二进制数变为一样
		//毕竟在异或中，只有两个位不同，才会有贡献
		//这里易得，添1和去1的操作，代价都是（1<<位数） 
		for(int k=1;k<=n;k<<=1){
			//if((i^k)>n) continue ;
			///cout << k << " " << endl;
			g[i].push_back({i^k,k*c});
		}
	}
	n*=2;
	for(; N <= n+1; N <<= 1);
	N>>=1;
	dijkstra(); 
	printf("%d",dis[t]);
	
	
	
	return 0;
}