牛客练习赛67 E-牛妹游历城市牛客竞赛

牛客练习赛67 E-牛妹游历城市
链接：https://ac.nowcoder.com/acm/contest/6885/E
来源：牛客网
题目描述

最近，牛妹天天宅在家里，真是憋死人了。他决定出去旅游。

文章图片

输入描述:
本题有多组数据。
第一行，输入一个数T，表示数据组数。
接下来2*T行，先输入一个数n，再输入n个数，第i个数表示a i。
输出描述:
对于每组数据，输出最小的行走距离。
如果无法从1号点到达n号点，则输出“Impossible”（不含引号）。
示例1
输入

2 6 2 3 5 8 13 21 12 1 2 3 4 5 6 7 8 9 10 11 12

输出

3 5

示例2
输入

5 3 1 2 3 4 177 188 199 211 2 1 2 4 1 1 1 1 5 1 2 4 8 16

输出

1 1 Impossible 1 Impossible

【牛客练习赛67 E-牛妹游历城市】备注:

数据保证1≤T≤5,1≤n≤105,1≤ai<232

题解:
先讲解一下lowbit：内部代码是x&-x，功能是取二进制x的从右到左第一个1。
分析一下题干，他说ai&aj != 0就有一条双向边，权值为lowbit（ai&aj）。那么就可以理解为它们如果i这个位子的值都为1，就进行连接。是通过这个点进行连接的。
下面提供两种做法，都是类似的：
第一种：
是一个分层图一样的思想，把32位分别建立出32个虚点，然后以这32个点建图（因为只有二进制位上都为1才能进行连接），就可以把nn的图优化成32n的一个图。对于每个，如果该二进制位j为1，那么连边权值为 1 << j（注意虚点到该点的距离为0，不然就要最后总数/2）。
Code：

#include #include #include #include #include #include #include #include #include #include #include #include #include #define ll long long using namespace std; const int INF=0x3f3f3f3f; const double pi=acos(-1.0),eps=1e-8; const ll mod=1e9+7; struct node { int to; ll w; friend bool operator <(node a,node b) { return a.w>b.w; } }; vector >mp[100505]; int vis[100505]; ll dis[100505]; void dijkstra() { priority_queueq; q.push(node{1,0}); dis[1]=0; while(!q.empty()) { node u=q.top(); q.pop(); if(vis[u.to]) continue; vis[u.to]=1; for(int i=0; i=dis[u.to]+t2) { dis[t1]=dis[u.to]+t2; q.push(node{t1,dis[t1]}); } } } } int main() { int T; scanf("%d",&T); while(T--) { for(int i=0; i<100505; i++) { mp[i].clear(); dis[i]=1e18; vis[i]=0; } int n; scanf("%d",&n); for(int i=1; i<=n; i++) { int c; scanf("%d",&c); for(int j=0; j<32; j++) { if(c&(1LL<




 第二种：
 方法也是异常的类似，毕竟题目就是这么一回事，主要是对于数位的处理。
 把每位数二进制中的1 当作一把钥匙，如果下一个数字的二进制位上也是1，那么代表这两个点是联通的，然后把最小的费用更新给32个位子上有1的点，这个点到下一个点的最小费用就更新成功了。
 Code：


 
#include
#include
#include
#include
#include
#include 
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;

const int INF=0x3f3f3f3f;

const double pi=acos(-1.0),eps=1e-8;

const ll mod=1e9+7;
int main()
{
int i,j,n,T;

long long x,one=1,t,Min[35];

scanf("%d",&T);

while(T--)
{
scanf("%d",&n);

t=0,memset(Min,0x3f,sizeof(Min));

for(i=0;
 i




		  	

    
    




    
    
    


推荐阅读

           
                  
              
                  redis高并发解决方案 redis100万并发 
                
                   
                
              
            

                  
              
                  成都空调安装电话 
                
                   
                
              
            

                  
              
                  佳能ip100废墨 
                
                   
                
              
            

                  
              
                  螃蟹能煮着吃吗 
                
                   
                
              
            

                  
              
                  关于go语言月薪多少钱的信息 
                
                   
                
              
            

                  
              
                  wOPPO Watch 2 发布！拥有4天续航 售价 1299 人民币起 
                
                   
                
              
            

                  
              
                  柯尼卡美能达205i复印机不喷墨的故障原因 
                
                   
                
              
            

                  
              
                  九州海上牧云记手游宠物怎么获得 宠物系统详解 
                
                   
                
              
            

                  
              
                  融资的钱亏了怎么办 融资多少钱 
                
                   
                
              
            

                  
              
                  天津长期护理保险制度是什么？ 
                
                   
                
              
            

                  
              
                  微波炉加热包子不变硬的方法 
                
                   
                
              
            

                  
              
                  Django框架之django|Django框架之django admin的命令行详解 
                
                   
                
              
            

                  
              
                  林内热水器错误代码88处理方法与故障原因介绍 ,自己可以先这样检修下 
                
                   
                
              
            

                  
              
                  spss因子分析时如何提高kmo值 
                
                   
                
              
            

                  
              
                  摄影基地简介 摄影基地介绍 
                
                   
                
              
            

                  
              
                  阿里斯顿热水器显示屏常亮盾牌图标 阿里斯顿电热水器显示器闪烁 
                
                   
                
              
            

                  
              
                  去掉海蜇咸味方法视频 去掉海蜇咸味方法 
                
                   
                
              
            

                  
              
                  wey和长城有什么区别 长城WEY和哈弗的关系是什么 
                
                   
                
              
            

                  
              
                  斜视的偏方 中医治疗斜视偏方 
                
                   
                
              
            

                  
              
                  记单词 安卓,三款单词防遗忘软件让你牢记 
                
                   
                
              
            

          

牛客练习赛67 D-牛妹爱数列