链接：https://ac.nowcoder.com/acm/contest/26077/1006
来源：牛客网
题目描述
企鹅国中有NNN座城市，编号从111到NNN。
对于任意的两座城市iii和jjj，企鹅们可以花费(i xor j)∗C(i\,\,xor\,\, j)*C(ixorj)∗C的时间从城市iii走到城市jjj，这里CCC为一个给定的常数。
当然除此之外还有MMM条单向的快捷通道，第i条快捷通道从第FiF_iFi个城市通向第TiT_iTi个城市，走这条通道需要消耗ViV_iVi的时间。
现在来自Penguin Kingdom University的企鹅豆豆正在考虑从城市AAA前往城市BBB最少需要多少时间？
输入描述:
输入第一行包含三个整数N,M,C，表示企鹅国城市的个数、快捷通道的个数以及题面中提到的给定的常数C。i
接下来的M行，每行三个正整数F
,Ti
,Vi
(1≤Fi
≤N,1≤Ti
≤N,1≤Vi
≤100)，分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。
最后一行两个正整数A,B(1≤C≤100)，表示企鹅豆豆选择的起点城市标号和终点城市标号。
输出描述:
输出一行一个整数，表示从城市 A 前往城市 B 需要的最少时间。示例1
输入
复制4 2 1 1 3 1 2 4 4 1 4
输出
复制5
说明
直接从 1 走到 4 就好了。示例2
输入
复制7 2 10 1 3 1 2 4 4 3 6
输出
复制34
说明
先从 3 走到 2 ，再从 2 通过通道到达 4 ，再从 4 走到 6。
备注:
分析
图片太小了，看了别人的提交才知道数据范围是1e7。。。
这道题加入了 i ^ j 为两点距离。如果暴力跑1e10会超时。所以需要根据位运算的特性精简边数。
i 和 j 的差别就是 1 的位置和数量。
首先先忽略直通路径
对于每对i ，j来说。从i 到 j 有两种方式
一种是i 经过其它点k 到达 j 花费是 i ^ k + k ^ j
一种是i 直接到达 j 花费是i ^ j
如果k 的1 的位置都和 i 与 j 重复，那多一个k 就多了差不多一倍的消耗
每个点到另一个点都是选择直接走到另一个点而不借助其它点的花费最少
对最短路长度的贡献，取决于两者不同1的位置和数量，一旦引入其它点会导致位数贡献变多，不是最优
现在把贡献拆开，i 和 j 的位置差别可能不止一位。要使i 变成 j ，i 就需要把自己连向和自己只差一位的点，这样经过有限次变动，i 就可以变成 j。每次移动都是 i 和 j 不同的位数 所以答案不会变差。
按照这样精简边数就可以跑最短路。
//-------------------------代码----------------------------
//#define int ll
const int N = 1e7+10;
int n,m,c;
int e[N],ne[N],w[N],h[N],idx;
int dist[N];bool vis[N];
void add(int a,int b,int c) {
e[idx] = b,ne[idx] = h[a],w[idx] = c,h[a] = idx++ ;
}
int st,ed;
void dij() {
ms(dist,0x3f);
ms(vis,0);
priority_queue<pii,V<pii>,greater<pii>> q;
q.push({0,st});
dist[st] = 0;
while(q.size()) {
auto t = q.top();q.pop();
int ver = t.second,W = t.first;
if(vis[ver]) continue;
vis[ver] = 1;
for(int i = h[ver];~i;i=ne[i]) {
if(vis[e[i]]) continue;
if(dist[e[i]] > W + w[i]) {
dist[e[i]] = dist[ver] + w[i];
q.push({dist[e[i]],e[i]});
}
}
}
}
void solve()
{
cin>>n>>m>>c;
ms(h,-1);
fo(i,1,m) {
int x,y,z;cin>>x>>y>>z;
add(x,y,z);
}
fo(i,0,n) {
for(int j = 1;j<=n;j<<=1) {
if((i ^ j) > n)continue;
add(i,i^j,j*c);
}
}
cin>>st>>ed;
dij();
cout<<dist[ed]<<endl;
}
void main_init() {}
signed main(){
AC();clapping();TLE;
cout<<fixed<<setprecision(12);
main_init();
// while(cin>>n,n)
// while(cin>>n>>m,n,m)
// int t;cin>>t;while(t -- )
solve();
// {solve(); }
return 0;
}
/*样例区
*/
//------------------------------------------------------------
标签：dist,int,城市,dijkstra,cin,vis,异或,1006,ver From： https://www.cnblogs.com/er007/p/16597037.html