P1613 跑路【倍增】【最短路】

题目描述

小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<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

输出 #1<button class="copy-btn lfe-form-sz-middle" data-v-370e72e2="" data-v-52f2d52f="" type="button">复制</button>

说明/提示

【样例解释】

1->1->2->3->4，总路径长度为4千米，直接使用一次跑路器即可。

【数据范围】

50%的数据满足最优解路径长度<=1000；

100%的数据满足n<=50，m<=10000，最优解路径长度<=maxlongint。

思路

　　由于数据量很小，可以考虑Floyd，而由于空间跳跃的缘故，直接跑Floyd出来的最短路不一定是真正的最短路。

　　于是用倍增的思想来维护一下两点间的最短路。

　　可以建立一个bool倍增数组 f[i][j][k] 来表示点对 i，j 间可以由空间跳跃一次跳达。

　　如何处理出所有的这样的点对。

　　可以枚举 K 跑 Floyd。因为是边权小于Maxlongint的，所以在 1 ~ 64 的范围内枚举k就可以了。

　　令中转点为 t ，显然如果 i 到 t 是 2^(k-1) 的距离，且 t 到 k 是 2^(k-1) 的距离，就知道一定有 i -> j 是 2 ^ k 的距离，此时更新 f[i][j][k] 和 dis[i][j] 即可。

ＣＯＤＥ

 1 #include <bits/stdc++.h>
 2 #define dbg(x) cout << #x << "=" << x << endl
 3 #define eps 1e-8
 4 #define pi acos(-1.0)
 5 
 6 using namespace std;
 7 typedef long long LL;
 8 
 9 template<class T>inline void read(T &res)
10 {
11     char c;T flag=1;
12     while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
13     while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
14 }
15 
16 namespace _buff {
17     const size_t BUFF = 1 << 19;
18     char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
19     char getc() {
20         if (ib == ie) {
21             ib = ibuf;
22             ie = ibuf + fread(ibuf, 1, BUFF, stdin);
23         }
24         return ib == ie ? -1 : *ib++;
25     }
26 }
27 
28 int qread() {
29     using namespace _buff;
30     int ret = 0;
31     bool pos = true;
32     char c = getc();
33     for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
34         assert(~c);
35     }
36     if (c == '-') {
37         pos = false;
38         c = getc();
39     }
40     for (; c >= '0' && c <= '9'; c = getc()) {
41         ret = (ret << 3) + (ret << 1) + (c ^ 48);
42     }
43     return pos ? ret : -ret;
44 }
45 
46 const int maxn = 1e4 + 7;
47 
48 int n,m;
49 
50 bool f[100][100][100];
51 int dis[100][100];
52 
53 void init() {
54     for ( int i = 1; i <= n; ++i ) {
55         for ( int j = 1; j <= n; ++j ) {
56             if(i == j) {
57                 dis[i][j] = 0;
58             }
59             else {
60                 dis[i][j] = 0x3f3f3f3f;
61             }
62         }
63     }
64 }
65 
66 int main()
67 {
68     scanf("%d %d",&n, &m);
69     init();
70     int u, v;
71     for ( int i = 1; i <= m; ++i ) {
72         scanf("%d %d",&u, &v);
73         dis[u][v] = 1;
74         f[u][v][0] = 1;
75     }
76     for (int t = 1; t <= 64; ++t) {
77         for (int k = 1; k <= n; ++k) {
78             for (int i = 1; i <= n; ++i) {
79                 for (int j = 1; j <= n; ++j) {
80                     if(f[i][k][t-1] && f[k][j][t-1]) {
81                         f[i][j][t] = 1;
82                         if(i != j) dis[i][j] = 1;
83                         else
84                             dis[i][j] = 0;
85                     }
86                 }
87             }
88         }
89     }
90     for (int k = 1; k <= n; ++k) {
91         for (int i = 1; i <= n; ++i) {
92            for (int j = 1; j <= n; ++j) {
93                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
94             }
95         }
96     }
97     printf("%d\n",dis[1][n]);
98     return 0;
99 }