题解 | #最短路#

本题主要坑点在于无脑加边会超时,顺便吐槽那个xoj操作wa了几发才看出来是异或操作.

点和点的边权为
即和它们的位有关系，可以从位的关系入手，精简边数
不考虑单向通道的情况下，,之间的最短距离应是 ,即不假借其他点而直接转移过来。对最短路长度的贡献取决于二者不同位的个数和位置。一旦引入中间结点,又导致位数贡献变多，不是最优。
现在可以把贡献拆开,和两点的不同位数可能不止一位。所有的点都连向和自己只相差一位的点，这样经过有限次位数的变动，可以使得变成,且每次变动的都是与不同的位数,因此答案不会变差。
按照上述精简边数建图跑最短路即可

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,M=5e6+10;
int h[N],e[M],ne[M],w[M],idx;
int dist[N];
bool st[N];
using pii=pair<int,int>;
void add(int a,int b,int c){
    e[idx]=b;
    w[idx]=c;
    ne[idx]=h[a];
    h[a]=idx++;
}
int main(){
    int n,m,C;
    priority_queue<pii,vector<pii>,greater<pii>>pq;
    scanf("%d %d %d",&n,&m,&C);
    memset(h,-1, sizeof h);
    for(int i=0;i<m;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        add(a,b,c);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j<<=1){
            if((i^j)>n)continue;
            add(i,(i^j),j*C);//加边
        }
    }
    int beg,end;
    scanf("%d %d",&beg,&end);
    memset(dist,0x3f, sizeof dist);
    dist[beg]=0;
    pq.push({0,beg});
    while(!pq.empty()){
        pii t=pq.top();
        #define F first
        #define S second
        pq.pop();
        if(st[t.S])continue;
        st[t.S]=true;
        for(int i=h[t.S];~i;i=ne[i]){
            int j=e[i];
            if(dist[j]>dist[t.S]+w[i]){
                dist[j]=dist[t.S]+w[i];
                if(!st[j])
                pq.push({dist[j],j});
            }
        }
    }
    cout<<dist[end];

}