牛客练习赛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




		  	

    
    




    
    
    


推荐阅读

           
                  
              
                  南宁：房贷利率新政实施后买房能省多少钱？ 
                
                   
                
              
            

                  
              
                  drive|希捷推出 Xbox 专用外置 SSD：1TB 约 1095元，USB 3.2 Gen1 接口 
                
                   
                
              
            

                  
              
                  农户贷款如何界定 「一般农户指什么」 
                
                   
                
              
            

                  
              
                  java用什么软件写代码，JAVA用什么软件编写 
                
                   
                
              
            

                  
              
                  不要吃发物 不要吃过甜过咸和酸性的食物 
                
                   
                
              
            

                  
              
                  八角金盘的介绍-八角金盘的作用 
                
                   
                
              
            

                  
              
                  flutter添加横线，flutter虚线边框 
                
                   
                
              
            

                  
              
                  为什么戒烟后会发胖？ 
                
                   
                
              
            

                  
              
                  佛珠多肉烂根怎么办 佛珠多肉烂了怎么办 
                
                   
                
              
            

                  
              
                  中国知名菜刀有什么牌子？中国十大菜刀品牌排行 
                
                   
                
              
            

                  
              
                  从入门到精通，轻松应对各种错误 打印机1700代码解析 
                
                   
                
              
            

                  
              
                  水果礼盒制作步骤大全图解 水果礼盒的制作技巧是怎么样的 
                
                   
                
              
            

                  
              
                  支付宝花呗当面花怎么使用？使用方法及店铺详细介绍 
                
                   
                
              
            

                  
              
                  恒为科技的军方服务器具有怎样的性能？ 恒为科技军方服务器怎么样 
                
                   
                
              
            

                  
              
                  gis中画的图成无效的书签，gis图没了 
                
                   
                
              
            

                  
              
                  工商银行主要业务有哪些 
                
                   
                
              
            

                  
              
                  iphone皮套 
                
                   
                
              
            

                  
              
                  爱普生1430喷墨机清零 
                
                   
                
              
            

                  
              
                  关于vb.neteval的信息 
                
                   
                
              
            

                  
              
                  非诚勿扰影视产业分析 
                
                   
                
              
            

          

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