洛谷4366——最短路（dijkstra，思维，异或）

题目大意
给定一个n个点，m条边的图，每条边有边权，而每个点\(i\)也可以直接到达\(j\)，代价是\(i\ xor\ j\)，给定一个S和T，求S到T的最小代价
其中\(n\le100000,m\le100000\)

一看这个数据范围，我们就知道显然不能建图~
那么就需要一点小技巧了

就是说，一条边可以由好几部分的边组合而成，而且代价还是相等的

注意 0 号结点也需要考虑（有可能两个节点编号按位与为0 ），并把异或值控制在 n 以内（出了 n 范围的点一定可以用 0号节点解决）

所以对于节点\(x\)我们只需要将他向 \(x\ xor \ 2^k\)连边就可以~
因为通过这个中转节点，他就可以到其他的能到的点，而且权值也是一样的

#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<map> #include<queue> #include<vector> #define pa pair< int , int > using namespace std;inline int read() {int x=0,f=1;char ch=getchar();while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}return x*f; }const int maxn = 1e5+1e2; const int maxm = 4e6+1e2;int point[maxn],nxt[maxm],to[maxm],val[maxm]; int n,m; int vis[maxn],dis[maxn]; int cnt; int s,t; priority_queue<pa,vector<pa>,greater<pa> > q;void addedge(int x,int y,int w) {nxt[++cnt]=point[x];to[cnt]=y;val[cnt]=w;point[x]=cnt; }int c;void dijkstra(int s) {memset(dis,127/3,sizeof(dis));memset(vis,0,sizeof(vis));dis[s]=0;q.push(make_pair(0,s));while (!q.empty()){int x = q.top().second;q.pop();if (vis[x]) continue;vis[x]=1;for (int i=point[x];i;i=nxt[i]){int p = to[i];if (dis[p]>dis[x]+val[i]){dis[p]=dis[x]+val[i];q.push(make_pair(dis[p],p));}}} }int main() {scanf("%d%d%d",&n,&m,&c);for (int i=1;i<=m;++i){int x=read(),y=read(),w=read();addedge(x,y,w);}for (int i=0;i<=n;++i){for (int j=1;j<=n;j<<=1){int tmp = (i^j);if (tmp>n) continue;addedge(i,tmp,j*c);}}cin>>s>>t;dijkstra(s);cout<<dis[t]<<endl;return 0; }

转载于:https://www.cnblogs.com/yimmortal/p/10160753.html

总结

以上是生活随笔为你收集整理的洛谷4366——最短路（dijkstra，思维，异或）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。