本文主要是介绍炫酷路途，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
【题目描述】
小希现在要从寝室赶到机房，路途可以按距离分为N段，第i个和i+1个是直接相连的，只需要一秒钟就可以相互到达。
炫酷的是，从第i个到第i+2p个也是直接相连的（其中p为任意非负整数），只需要一秒钟就可以相互到达。
更炫酷的是，有K个传送法阵使得某些u,v之间也是直接相连的，只需要一秒钟就可以相互到达，当然，由于设备故障，可能会有一些u=v的情况发生。
现在小希为了赶路，她需要在最短的时间里从寝室(编号为1)到达机房(编号为N)，她不希望到达这N个部分以外的地方（不能到达位置N+1），也不能走到比自己当前位置编号小的地方（比如从5走到3是非法的）。
她想知道最短的时间是多少。
【输入描述】
第一行输入两个整数N,K，表示路途的段数和传送法阵的数量。
从第二行开始K行，每行两个整数ai,bi表示两个位置之间相连。
2≤N≤1,000,000,000
0≤K≤15【输出描述】
输出一个整数，表示从寝室到机房最短的时间是多少秒。
【样例】
示例1
输入
12 2
1 5
6 6
输出
3示例2
输入
17 2
2 5
8 9
输出
1
思路：
n 很大很吓人但其实影响不大，实际上将所有额外连边的 k*2 个点再加上起点、终点就可以构成一张图，最多只有 32 个点，然后计算两点间的距离求最短路即可
【源代码】
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#define PI acos(-1.0)
#define E 1e-6
#define INF 0x3f3f3f3f
#define N 3001
#define LL long long
const int MOD=1e9+7;
using namespace std;
int n,m;
struct Edge{int x,y;
}edge[N];
struct Node{int x,w;Node(){}Node(int x,int w):x(x),w(w){}bool operator < (const Node &rhs)const{return w>rhs.w;}
};
vector<int> mp;//图
int G[N][N];//边权
int res[N];
bool vis[N];
int bit(int x){//计算x中1的个数int cnt=0;while(x){if(x&1)cnt++;x>>=1;}return cnt;
}
int calculate(int x){//计算图中第一个大于等于x的位置return lower_bound(mp.begin(),mp.end(),x)-mp.begin();
}
void dijkstra(){memset(res,INF,sizeof(res));res[0]=0;priority_queue<Node> Q;Q.push(Node(0,0));while(!Q.empty()){int x=Q.top().x;int w=Q.top().w;Q.pop();vis[x]=true;for(int y=0;y<mp.size();y++){if(!vis[y]&&w+G[x][y]<res[y]){res[y]=w+G[x][y];Q.push(Node(y,res[y]));}}}
}
int main(){cin>>n>>m;int cnt=0;for(int i=0;i<m;i++){int x,y;cin>>x>>y;if(x!=y&&x<=n&&y<=n){if(x>y)//序号小者在前，保证边是有向的swap(x,y);//存点mp.push_back(x);mp.push_back(y);//存边edge[cnt].x=x;edge[cnt].y=y;cnt++;}}mp.push_back(1);//起点mp.push_back(n);//终点sort(mp.begin(),mp.end());mp.erase(unique(mp.begin(),mp.end()),mp.end());//去重//计算边权memset(G,INF,sizeof(G));for(int i=0;i<mp.size();i++)for(int j=i+1;j<mp.size();j++)G[i][j]=min(G[i][j],bit(mp[j]-mp[i]));for(int i=0;i<cnt;i++)G[calculate(edge[i].x)][calculate(edge[i].y)]=min(G[calculate(edge[i].x)][calculate(edge[i].y)],1);dijkstra();cout<<res[mp.size()-1]<<endl;return 0;
}
这篇关于炫酷路途的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
