Luogu P4366 [Code+#4]最短路

Luogu P4366 [Code+#4]最短路"/>

Luogu P4366 [Code+#4]最短路

题目背景

在北纬 91° ，有一个神奇的国度，叫做企鹅国。这里的企鹅也有自己发达的文明，称为企鹅文明。因为企鹅只有黑白两种颜色，所以他们的数学也是以二进制为基础发展的。

比如早在 1110100111101001 年前，他们就有了异或这样一个数学概念。如果你不知道异或是什么，请出门过墙左转到这里。

再比如早在 10000101000010 年前，他们的大科学家 Penguin. Tu 就提出了图和最短路径这样一些概念。

题目描述

企鹅国中有 NN 座城市，编号从 11 到 NN 。

对于任意的两座城市 ii 和 jj ，企鹅们可以花费 (i~\mathrm{xor}~j) \times C(i xor j)×C 的时间从城市 ii 走到城市 jj ，这里 CC 为一个给定的常数。

当然除此之外还有 MM 条单向的快捷通道，第 ii 条快捷通道从第 F_iFi​​​ 个城市通向第 T_iTi​​​ 个城市，走这条通道需要消耗 V_iVi​​​ 的时间。

现在来自 Penguin Kingdom University 的企鹅豆豆正在考虑从城市 AA 前往城市 BB 最少需要多少时间？

输入输出格式

输入格式：

从标准输入读入数据。

输入第一行包含三个整数 N,M,CN,M,C ，表示企鹅国城市的个数、快捷通道的个数以及题面中提到的给定的常数CC。

接下来的 MM 行，每行三个正整数 F_i,T_i,V_iFi​,Ti​,Vi​​ (1 \leq F_i \leq N1≤Fi​≤N,1 \leq T_i \leq N ,1\leq V_i \leq 1001≤Ti​≤N,1≤Vi​≤100)，分别表示对应通道的起点城市标号、终点城市标号和通过这条通道需要消耗的时间。

最后一行两个正整数 A,BA,B (1 \leq C \leq 100)(1≤C≤100)，表示企鹅豆豆选择的起点城市标号和终点城市标号。

输出格式：

输出到标准输出。

输出一行一个整数，表示从城市 AA 前往城市 BB 需要的最少时间。

输入输出样例

输入样例#1： 复制

4 2 1
1 3 1
2 4 4
1 4

输出样例#1： 复制

5

输入样例#2： 复制

7 2 10
1 3 1
2 4 4
3 6

输出样例#2： 复制

34

说明

样例1解释

直接从 11 走到 44 就好了。

样例2解释

先从 33 走到 22 ，再从 22 通过通道到达 44 ，再从 44 走到 66。

观察一下，最短联想到最短路

再思考一下xor的性质

001——》000——》100与001——》100是等价的

所以每个点只用与只有1位不同的点连边，也就是最多与lg n个点相连

dijkstra

注意这是单向边

#include<cstdio>
#include<queue>
#define ll long long
using namespace std;
int read()
{int ret=0;char ch=getchar();while(ch<'0'||ch>'9') ch=getchar();while(ch>='0'&&ch<='9')ret=(ret<<1)+(ret<<3)+ch-'0',ch=getchar();return ret;
}int n,m,c,cnt;
const int N=2e6+5,M=1e7+5;
int he[N],nxt[M],to[M];
ll w[M],dis[N];
bool fl[N];struct NA{int id;ll x;
};
bool operator >(NA i,NA j)
{return i.x>j.x;
}
priority_queue<NA,vector<NA>,greater<NA> >q;
inline void add(int u,int v,int k)
{nxt[++cnt]=he[u];to[cnt]=v;w[cnt]=k;he[u]=cnt;
}int main()
{n=read(); m=read(); c=read();for(int i=1;i<=m;i++){int u=read(),v=read(),k=read();add(u,v,k); }for(int i=0;i<=n;i++)for(int j=0;j<20;j++)if((i^(1<<j))<=n)add(i,i^(1<<j),(1<<j)*c);int A=read(),B=read();for(int i=0;i<=n;i++) dis[i]=1e18;dis[A]=0; q.push((NA){A,0});for(int i=0;i<=n;i++){while(!q.empty()&&fl[q.top().id]) q.pop();if(q.empty()) break;int u=q.top().id;if(u==B) break;fl[u]=1;q.pop();for(int e=he[u];e;e=nxt[e]){int v=to[e];if(!fl[v]&&dis[v]>dis[u]+w[e])q.push((NA){v,dis[v]=dis[u]+w[e]});}}printf("%lld\n",dis[B]);return 0;
}