题目链接：https://ac.nowcoder.com/acm/contest/28848/A

题目大意

企鹅国中有N座城市，编号从1到N。
对于任意的两座城市i和j，企鹅们可以花费(i xor j) * C （xor表示异或）的时间从城市i走到城市j，这里C为一个给定的常数。
当然除此之外还有M条单向的快捷通道，第i条快捷通道从第F_i个城市通向第T_i个城市，走这条通道需要消耗V_i的时间。
现在来自Penguin Kingdom University的企鹅豆豆正在考虑从城市A前往城市B最少需要多少时间？

具体输入输出和数据范围请看原题。

思路

毫无疑问是考最短路的，所以想到dijkstra来处理无负边权的图。可是这里任意两个点之间都可以连通，这将会是个完全图（任意两点都连通的图），复杂度会达到惊人的O((N^2+M)logN)，当务之急是减少边的数量。

不难发现，题目中i xor j的条件十分亮眼。

考虑到异或的性质，假如我要从5(101)走到 9(1001)，括号内为二进制，可以5(0101) -> 1(0001) -> 9(1001)这样的开销和直接从5走到9的开销相同。步骤是先消去不需要的1，再加上需要的1，这样一来，边的条数就从N^2减少到NlogN，这多是一件美事啊。注意当起点为2的幂的时候，可能走到0这个点，所以我们在增加异或边的时候需要假设 0 这个点。

代码

/* Copyright (C) 2022 ErikTse */
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <map>
#include <set>
#include <bitset>
#include <queue>
#include <utility>
#include <stack>
#include <algorithm>
#define pb push_back
#define fi first
#define se second
#define pr printf
#define sc scanf
#define gc getchar
#define int long long//注意使用%lld输出long long类型数据
using namespace std;
inline int readInt(){//快速读入int
	int s = 0,w = 1;char c = gc();
	while(c > '9' || c < '0')if(c == '-')w = -1,c = gc();
	while('0' <= c && c <= '9')s = s * 10 + c - '0',c = gc();
	return s * w;
}
inline string readString(){//快速读入string
	string s;char c = gc();
	while(c == ' ' || c == '\n' || c == '\r')c = gc();
	while(c != ' ' && c != '\n' && c != '\r')s += c,c = gc();
	return s;
}
/*-------全局变量------*/
const int maxn = 1e5 + 10;
struct Node
{
	int x, d;
	//重载运算符 
	bool operator < (const Node &m)const{return d > m.d;}
};
int N, M, C;
vector<vector<Node> > g;//邻接表， 
int d[maxn];
/*-----自定义函数------*/

inline int dijkstra(int A,int B)
{
	memset(d, 127, sizeof d);
	priority_queue<Node> pq;//小根堆，堆顶为距离最小的点 
	pq.push({A, d[A] = 0});
	while(!pq.empty())
	{
		int x = pq.top().x;
		int dist = pq.top().d;
		pq.pop();
		if(x == B)return d[B];//第一次找到的 B 一定是最小距离 
		if(dist != d[x])continue;//dist为 A->B 的距离 
		//拓展 
		for(auto i : g[x])//i为下一个节点 
			if(d[i.x] > dist + i.d)//如果 A->i 大于  A->B->i
				pq.push({i.x, d[i.x] = dist + i.d});
	}
    return 0;
}

signed main()
{
	//freopen("in.txt","r",stdin);
	N = readInt(), M = readInt(), C = readInt();
	g.resize(N + 1);
	//读入边
	while(M --)
	{
		int x = readInt(), y = readInt(), v = readInt();
		g[x].pb({y, v});
	}
	//添加异或边（二进制优化）
	for(int i = 0;i <= N; ++ i)//0 需要作为中转点 
	{
		for(int j = 1;j <= N; j *= 2)
			if((i ^ j) <= N)g[i].pb({i ^ j, j * C});
	}
	int A = readInt(), B = readInt();
	pr("%lld\n",dijkstra(A, B));
	return 0;
}