自动搬运

查看原文

来自洛谷，原作者为

	Mirach 诶这里还可以填东西？

搬运于2025-08-24 21:59:25，当前版本为作者最后更新于2018-04-13 17:00:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Problem

想要数据的可以去Code+上下载

题意： 给定$n$个点，求从$s$到$t$的最短路径，其中有两种走法（可以混搭）：一种是走给定的$m$有向边$(u_i,v_i,w_i)$；另一种可以由任意点$x$到任意点$y$，其费用是$c*(x$ $xor$ $y)$

Solution

明显不能直接$n^2$建边，为了多骗点分可能会想到可以dijkstra在过程中在线加边，处理到重点为止

但这样的最坏复杂度依旧是跑不过的（code+上这题的测试点有99个，骗分基本骗不满）

本着在任意一个正解中绝对不可能处理所有的$n^2+m$条边，发现有一些边可以被其他边替代，比如两个数异或值二进制表示中有两个及以上的1，那么可以用值分别为这两个1的边合并而成

比如：$3$ $xor$ $6$ $= 5$ $\Leftrightarrow$ $11_2$ $xor$ $110_2 = 101_2$ 5 二进制下有之间有两个 1 那么这个值可以由 $100_2$ 和 $1_2$这两个值合并而得 即边$(3,6)=(3,7)+(7,6)$ 其权值对应为 $101_2$ $100_2$ $1_2$

则对于任意点$x$，只用考虑给定边和到$\{v|v=x$ $xor$ $2^k,k\in N,v<=n\}$的边即可，其他边的效用定可以被这些边的组合包含，则对于点$x$，第二类边只有$\log_2x$条

则问题简化到只有$n\log n+m$条边了，$SPFA$目测会挂（有99个测试点），用$dijkstra$（博主用的是$dijkstra$的线段树优化）

注意$0$号结点也需要考虑（有可能两个节点编号按位与为$0$），并把异或值控制在$n$以内（出了$n$范围的点一定可以用$0$号节点解决）

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rg register
#define cl(x) memset(x,0,sizeof(x))
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)>0?(x):(-(x)))

template <typename _Tp> inline _Tp read(_Tp&x){
	rg char c11=getchar(),ob=0;x=0;
	while(c11^'-'&&!isdigit(c11))c11=getchar();if(c11=='-')c11=getchar(),ob=1;
	while(isdigit(c11))x=x*10+c11-'0',c11=getchar();if(ob)x=-x;return x;
}

const int N=201000,M=1001000,inf=2147483647;
struct Edge{int v,w,nxt;}a[M];
int head[N],dis[N],seg[N<<2];
char bo[N];
int n,m,c,_,ds,s,t;

inline void add(int u,int v,int w){a[++_].v=v,a[_].w=w,a[_].nxt=head[u],head[u]=_;}

#define mid (((l)+(r))>>1)

inline void build(int l,int r,int x){
	if(l==r){seg[x]=inf;return ;}
	build(l,mid,x<<1);
	build(mid+1,r,x<<1|1);
	seg[x]=inf;
	if(~seg[x<<1])seg[x]=min(seg[x],seg[x<<1]);
	if(~seg[x<<1|1])seg[x]=min(seg[x],seg[x<<1|1]);
	return ;
}

inline void update(int l,int r,int x,int pos,int t){
	if(l==r){seg[x]=min(seg[x],t);return ;}
	if(pos<=mid)update(l,mid,x<<1,pos,t);
	else update(mid+1,r,x<<1|1,pos,t);
	seg[x]=inf;
	if(~seg[x<<1])seg[x]=min(seg[x],seg[x<<1]);
	if(~seg[x<<1|1])seg[x]=min(seg[x],seg[x<<1|1]);
	return ;
}

inline int query(int l,int r,int x){
	if(l==r){ds=seg[x];return l;}
	if(seg[x]==seg[x<<1])return query(l,mid,x<<1);
	else if(seg[x]==seg[x<<1|1])return query(mid+1,r,x<<1|1);
	else return -1;
}

#undef mid

void spath(){
	build(0,n,1);
	update(0,n,1,s,0);
	while(!bo[t]){
		rg int x=query(0,n,1);
		bo[x]=1;dis[x]=ds;
		update(0,n,1,x,-1);
		for(rg int i=head[x];i;i=a[i].nxt)
			if(!bo[a[i].v])update(0,n,1,a[i].v,dis[x]+a[i].w);
		for(rg int i=1;i<=n;i<<=1)
			if(!bo[x^i]&&(x^i)<=n)update(0,n,1,x^i,dis[x]+c*i);
	}
	return ;
}

int main(){
	read(n);read(m);read(c);
	for(rg int i=0,x,y,z;i<m;++i)read(x),read(y),read(z),add(x,y,z);
	read(s);read(t);
	spath();
	printf("%d\n",dis[t]);
	return 0;
}