锐客网

  1. 首页 > it技术 > >

codeforces|Codeforces 845G Shortest Path Problem

codeforces线性基

原题 codeforces845G
题意 给一个无向带权图，求1-n的异或最短路。
解题思路 【codeforces|Codeforces 845G Shortest Path Problem】因为我们是在异或的情况下求最短路，因此环是一个特殊的存在。
我们从一个点走向环，在环内绕一圈再回到当前点，我们只会获得环的权值。也就是说，对于一个环的权值，我们可以只考虑选与不选。
如果我们在dfs遍历整个图的过程中，拆掉回边，图就成了一棵树。我们可以记录下i号点到1号点的异或距离d[i]，那么任意两个点u、v之间的距离可以用d[u]^d[v]表示。
假设在dfs的时候我们找到了一条连接u、v，权值为x的回边，相当于我们就找到了一个权值为d[u]^d[v]^x的环。
将环的权值放入线性基，答案相当于就是将d[n]与线性基内的数异或能取到的最小值。
代码

#include using namespace std; const int N=1e5+10; struct Edge{ int to,next,cost; } way[N<<1]; int n,m,tot,num[N]; bool vis[N]; struct Base { int x[31]; void Insert(int v) { if (!v) return ; for (int i=30; i>=0; --i) if ((1<=0; --i) if ((v^x[i])

    推荐阅读


    上一篇：Java数据结构与算法|Java学习手册（（数据结构与算法-链表）如何实现单链表排序（））

    下一篇：Leetcode #35. Search Insert Position 搜寻插入位置 解题报告