洛谷1613跑路解题记录
题目描述
小A的工作不仅繁琐，更有苛刻的规定，要求小A每天早上在6：00之前到达公司，否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资，小A买了一个十分牛B的空间跑路器，每秒钟可以跑2^k千米（k是任意自然数）。当然，这个机器是用longint存的，所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图，小A家为点1，公司为点n，每条边长度均为一千米。小A想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证1到n至少有一条路径。
输入输出格式
输入格式：
第一行两个整数n，m，表示点的个数和边的个数。
接下来m行每行两个数字u，v，表示一条u到v的边。
输出格式：
一行一个数字，表示到公司的最少秒数。
输入输出样例
输入样例#1：
4 4
1 1
1 2
2 3
3 4
输出样例#1：
1
思路&题解：
最开始看到这道题的时候感觉这是道水题，直接spfa跑最短路，然后把最短路用倍增分解下就可以了。然后……大红大紫（ORZ）。后来不服气，看了题解，发现可以从自己跑到自己，因为有跑路器的缘故，所以有的时候最短的时间并不是对应最短路。因为跑路器可以在一秒的时间中跑（2^k）m所以我们可以开一个数组b[k][i][j]来记录i到j路径中有没有一条路径的长度时（2^k）m如果有就将dis[i][j]的值赋为1，然后跑最短路即可。下面贴代码吧。
1 #include<cstdio> 2 #include<cstring> 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 typedef long long LL; 7 const int N=55; 8 int dis[N][N]; 9 bool b[64][N][N]; 10 int n,m; 11 void Init() 12 { 13 memset(dis,0x7f,sizeof(dis)); 14 int i,x,y; 15 scanf("%d%d",&n,&m); 16 for(i=1;i<=m;i++) 17 { 18 scanf("%d%d",&x,&y); 19 dis[x][y]=1; 20 b[0][x][y]=1; 21 } 22 } 23 void floyd() 24 { 25 int i,j,k; 26 for(k=1;k<=n;k++) 27 { 28 for(i=1;i<=n;i++) 29 { 30 for(j=1;j<=n;j++) 31 { 32 if(dis[i][k]<=0x7fffff&&dis[k][j]<=0x7fffff) 33 { 34 dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); 35 } 36 } 37 } 38 } 39 } 40 void work() 41 { 42 int l,k,i,j; 43 for(l=1;l<=62;l++) 44 { 45 for(k=1;k<=n;k++) 46 { 47 for(i=1;i<=n;i++) 48 { 49 for(j=1;j<=n;j++) 50 { 51 if(b[l-1][i][k]&&b[l-1][k][j]) 52 { 53 dis[i][j]=1; 54 b[l][i][j]=1; 55 } 56 } 57 } 58 } 59 } 60 floyd(); 61 printf("%d",dis[1][n]); 62 } 63 int main() 64 { 65 Init(); 66 work(); 67 return 0; 68 }优质内容筛选与推荐>>
1、[Tarjan系列] 无向图e-DCC和v-DCC的缩点
2、在UpdatePanel中内嵌Javascript的问题以及解决方案
3、Ubuntu更换源
4、问个开发的版本小问题~
5、with（上下文的用法）以及其他知识点