题解 P4366 【[Code+#4]最短路】

· · 题解

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;
}