题目链接：https://ac.nowcoder.com/acm/contest/6885/E
题意
- 有n个点，每个点都有权值ai，点与点之间的边权值是lowbit（ai&aj），边权值为0不能走
- lowbit（i）表示i的二进制形式从后往前第一个1的位置开始，截取到末尾，比如lowbit（12）= 4。12的二进制是1100，从后往前第一个1的位置截取末尾就是100，就是4
- 求从1号点走到n号点的最短路径
- 点与点之间二进制对应位置存在都是1的情况下，才能走这条边。
- 贪心地走最短路，每次走权值最小的，并更新最小花费。
- dis数组表示从1号结点通过二进制第i位走到此节点时的最小花费。
- t表示走到此节点需要的最小花费，走完之后，需要将此结点二进制1的位置的dis更新取小。
- 1号点二进制是1的位置dis初始化为0，其他的取个大一点的数就行
#include
#define ll long long
using namespace std;
int main(){
int T;
scanf("%d",&T);
while(T--){
ll n,t=0,one=1,x,dis[40];
scanf("%lld",&n);
memset(dis,0x3f,sizeof(dis));
for(int i=0;
i 思路2
- 分层建图，加32个点，然后跑一边dijkstra。
文章图片
AC代码
#include
#define ll long long
#define ull unsigned long long
#define sc(a) scanf("%d",&a)
#define ss(a) scanf("%s",a)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int maxn = 1e5+50;
const ll inf = 1e18;
struct node{
int u;
ll w;
bool operator < (const node &a)const{
return w>a.w;
}
};
struct Eage{
int u,next;
ll w;
}eage[maxn*12];
ll dis[maxn];
int vis[maxn],head[maxn];
int n,x,cnt;
void add(int u,int v,ll w){
eage[cnt].u=v;
eage[cnt].w=w;
eage[cnt].next=head[u];
head[u]=cnt++;
}
void dijkstra(){
fill(vis,vis+maxn,0);
fill(dis,dis+maxn,inf);
dis[1]=0;
priority_queueq;
q.push({1,0});
while(q.size()){
node t=q.top();
q.pop();
int from=t.u;
if(vis[from])continue;
vis[from]=1;
for(int j=head[from];
~j;
j=eage[j].next){
int to=eage[j].u;
ll w=eage[j].w;
if(dis[from]+w 
