P1613 跑路
题目描述
小\(A\)的工作不仅繁琐，更有苛刻的规定，要求小\(A\)每天早上在\(6:00\)之前到达公司，否则这个月工资清零。可是小\(A\)偏偏又有赖床的坏毛病。于是为了保住自己的工资，小\(A\)买了一个十分牛B的空间跑路器，每秒钟可以跑\(2^k\)千米（\(k\)是任意自然数）。当然，这个机器是用\(long\) \(int\)存的，所以总跑路长度不能超过\(max\) \(long\) \(int\)千米。小\(A\)的家到公司的路可以看做一个有向图，小\(A\)家为点\(1\)，公司为点\(n\)，每条边长度均为一千米。小\(A\)想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证\(1\)到\(n\)至少有一条路径。
输入输出格式
输入格式：
第一行两个整数\(n\),\(m\)，表示点的个数和边的个数。
接下来m行每行两个数字\(u\),\(v\)，表示一条\(u\)到\(v\)的边。
输出格式：
一行一个数字，表示到公司的最少秒数。
说明
\(50\)%的数据满足最优解路径长度\(<=1000\)；
\(100\)%的数据满足\(n<=50\)，\(m<=10000\)，最优解路径长度\(<=\) \(max\) \(long\) \(int\)。
首先，要确保自己的语文水平苟的住，这个鬼机器，每秒跑\(2^kkm\)的话是要跑刚好那么长的，不能多也不能少。
那么岂不是代表，只有长为\(2^kkm\)的链才算是有效边吗?
我们把所有有效边连上，跑最短路不就行了嘛。
如何求有效边？
\(2^k?\)有没有想到什么？
\(2^k=2^{k-1}+2^{k-1}?\)
对，就是倍增啊！
令\(g[u][v][j]\)代表点\(u\)到点\(v\)存在或不存在长度为\(2^j\)的边。
当\(g[u][k][j-1]\)和\(g[k][v][j-1]\)同时存在时，
\(g[u][v][j]\)存在。（\(k\)是枚举的一维）
#include <cstdio>#include <cstring>#include <queue>using namespace std;const int N=52;int g[N][N][70],n,m;//g[i][j][k]表示i点到j点存在边权为2^k的路int g0[N][N];int read(){ int x=0;char c=getchar(); while(c<'0'||c>'9') c=getchar(); while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar();} return x;}queue <int > q;int used[N],dis[N];void spfa(){ memset(used,0,sizeof(used)); used[1]=1; memset(dis,0x3f,sizeof(dis)); dis[1]=0; q.push(1); while(!q.empty()) { int u=q.front(); q.pop(); used[u]=0; for(int v=1;v<=n;v++) if(g0[u][v]&&dis[v]>dis[u]+g0[u][v]) { dis[v]=dis[u]+g0[u][v]; if(!used[v]) { used[v]=1; q.push(v); } } }}int main(){ memset(g,0,sizeof(g)); memset(g0,0,sizeof(g0)); n=read(),m=read(); int u,v; for(int i=1;i<=m;i++) { u=read(),v=read(); g[u][v][0]=1; //f[u][v][0]=v; } for(int j=1;j<=64;j++) for(int k=1;k<=n;k++) for(u=1;u<=n;u++) for(v=1;v<=n;v++) if(g[u][k][j-1]&&g[k][v][j-1]) g[u][v][j]=1; for(u=1;u<=n;u++) for(v=1;v<=n;v++) for(int j=0;j<=64;j++) if(g[u][v][j]) { g0[u][v]=1; break; } spfa(); printf("%d\n",dis[n]); return 0;}2018.5.2
