题目背景
在北纬 91° ，有一个神奇的国度，叫做企鹅国。这里的企鹅也有自己发达的文明，称为企鹅文明。因为企鹅只有黑白两种颜色，所以他们的数学也是以二进制为基础发展的。
比如早在 111010011110100111101001 年前，他们就有了异或这样一个数学概念。如果你不知道异或是什么，请出门过墙左转到这里。
再比如早在 100001010000101000010 年前，他们的大科学家 Penguin. Tu 就提出了图和最短路径这样一些概念。
题目描述
企鹅国中有 NNN 座城市，编号从 111 到 NNN 。
对于任意的两座城市 iii 和 jjj ，企鹅们可以花费 (i xor j)×C(i~mathrm{xor}~j) imes C(i xor j)×C 的时间从城市 iii 走到城市 jjj ，这里 CCC 为一个给定的常数。
当然除此之外还有 MMM 条单向的快捷通道，第 iii 条快捷通道从第 FiF_iFi 个城市通向第 TiT_iTi 个城市，走这条通道需要消耗 ViV_iVi 的时间。
现在来自 Penguin Kingdom University SDFZ 的企鹅豆豆正在考虑从城市 AAA 前往城市 BBB 最少需要多少时间？
输入输出格式
输入格式：
从标准输入读入数据。
输入第一行包含三个整数 N,M,C，表示企鹅国城市的个数、快捷通道的个数以及题面中提到的给定的常数C。
接下来的 MMM 行，每行三个正整数 Fi,Ti,Vi (1≤Fi≤N1,1≤Ti≤N,1≤Vi≤100)，分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。
最后一行两个正整数 A,BA,BA,B (1≤C≤100)，表示企鹅豆豆选择的起点城市标号和终点城市标号。
输出格式：
输出到标准输出。
输出一行一个整数，表示从城市 A 前往城市 B 需要的最少时间。
题目分析
关于SPFA：它死了。讲真我不觉得在类似网格图的东西上用SPFA是什么好办法
但即使是Dijkstra也完全无法承受如此巨大的数据范围，所以一定不是暴力建边。
折腾一下可以发现一些神奇性质：我们可以试着把这些点转成二进制，与其一下把所有位都转化成需要的数字不如一位一位转化，反正边权和是一样的。
举个例子，从00000到11111，直接一步到边权位00000 xor 11111 = 11111，我们也可以00000 -> 00001 -> 00011 -> 00111 -> 01111 -> 11111，发现这样和原来的代价是一样的！
根据这样的性质，我们只要把x和x*2^k连边就可以了（这里读作“二的k次方”，“^”不表示xor）。
再加上玄学优化的Dijkstra就可以了，堆优化好像有点悬，得吸氧
Code
// luogu-judger-enable-o2 #include<iostream> #include<cstdio> #include<queue> #include<algorithm> #include<cctype> using namespace std; const int MAXN = 100000 + 5; const int MAXM = 500000 + 5; const int INF = 0x3f3f3f3f; inline int read() { int X = 0,w = 0;char ch = 0; while(!isdigit(ch)) {w |= ch == '-';ch = getchar();} while(isdigit(ch)) X = (X<<3)+(X<<1)+(ch^48),ch = getchar(); return w ? -X : X; } struct Edge { int nxt; int to,w; } l[MAXM + MAXN * 20]; struct Node { int id; int dis; friend bool operator < (Node x,Node y) { return x.dis > y.dis; } } a[MAXN]; int n,m,c; int s,t; int head[MAXN],cnt; int dis[MAXN]; bool vis[MAXN]; //priority_queue <pair,vector<pair>,greater<pair>> q; priority_queue<Node> q; void add(int x,int y,int z) { cnt++; l[cnt].nxt = head[x]; l[cnt].to = y; l[cnt].w = z; head[x] = cnt; return; } inline void dijkstra(int s) { // int cur; // memset(dis,127,sizeof(dis)); // dis[s] = 0; // q.push(pair(0,s)); // while(!q.empty()) { // cur = q.top().second; // tmp = q.top().first; // q.pop(); // if(tmp != dis[cur]) continue; // for(int i = head[cur];i;i = l[i].nxt){ // if(dis[l[i].to] > dis[cur] + l[i].w) { // dis[l[i].to] > dis[cur] + l[i].w // q.push(pair(dis[l[i].to],l[i].to)); // } // } // } // return; for(int i = 1;i <= n;i++) { a[i].dis = INF; a[i].id = i; } int cur; a[s].dis = 0; q.push(a[s]); while(!q.empty()) { cur = q.top().id; q.pop(); if(vis[cur]) continue; vis[cur] = true; for(int i = head[cur];i;i = l[i].nxt) { if(vis[l[i].to]) continue; if(a[l[i].to].dis > a[cur].dis + l[i].w) { a[l[i].to].dis = a[cur].dis + l[i].w; q.push(a[l[i].to]); } } } } int main() { scanf("%d%d%d",&n,&m,&c); int x,y,z; for(register int i = 1;i <= m;i++) { x=read(),y=read(),z=read(); add(x,y,z); } for(register int i = 0;i <= n;i++) { for(register int j = 1;j <= n;j <<= 1) { if((i ^ j) > n) continue; add(i,i^j,j*c); } } // for(int i = 1;i <= cnt;i++) {//DEBUG // cout<<"DEBUG: "<<i<<" "<<l[i].nxt<<" "<<l[i].to<<" "<<l[i].w<<endl; // } scanf("%d%d",&s,&t); dijkstra(s); printf("%d ",a[t].dis); // for(int i = 1;i <= n;i++) cout<<a[i].dis<<" "; return 0; }