[演算法心得] luogu 跑路

jimmyhealer

嗨大家好~ 我是新加入論壇的萌新，之後可能會每日更新一下演算法心得，那目前會在 c/c++ 版，如果大家很熱絡的話再申請 演算法/競賽程式 版吧!

--------------------------------------------------- 正文開始 ---------------------------------------------------

題目名稱: 跑路
題目網站: luogu
題目網址: https://www.luogu.com.cn/problem/P1613
題目內容:

小A的工作不仅繁琐，更有苛刻的规定，要求小A每天早上在6：00之前到达公司，否则这个月工资清零。可是小A偏偏又有赖床的坏毛病。于是为了保住自己的工资，小A买了一个十分牛B的空间跑路器，每秒钟可以跑2^k千米（k是任意自然数）。当然，这个机器是用longint存的，所以总跑路长度不能超过maxlongint千米。小A的家到公司的路可以看做一个有向图，小A家为点1，公司为点n，每条边长度均为一千米。小A想每天能醒地尽量晚，所以让你帮他算算，他最少需要几秒才能到公司。数据保证1到n至少有一条路径。

範例輸入 #1:
4 41 11 22 33 4
範例輸出 #1:
1
--------------------------------------------------- 題解心得 ---------------------------------------------------

看到題目講到每秒鐘能跑 2^k 公里，第一個想到的就是倍增。
所以接下來我們只要找出哪些路段可以在 1 秒內跑到即可。

1. #include<bits/stdc++.h>
   
2. #define ll long long
   
3. #define INF 0x3f3f3f3f
   
4. #define MOD 1000000007
   
5. #define io iOS::sync_with_stdio(0);cin.tie(0);cout.tie(0);
   
6. using namespace std;
   
7. const int MXN = 65;
   
8. 
   
9. //int ar[MXN];
   
10. 
    
11. void sol(){
    
12.   ll ans = 0, n = 0, m = 0, k = 0;
    
13. 
    
14.   cin >> n >> m;
    
15.   int dis[MXN][MXN] = {};
    
16.   int g[MXN][MXN][MXN] = {};
    
17.   memset(dis, 10, sizeof(dis));
    
18.   for(int i = 0; i < m; ++i){
    
19.     int u, v;
    
20.     cin >> u >> v;
    
21.     dis[u][v] = 1;
    
22.     g[u][v][0] = 1;
    
23.   }
    
24.   for(int i = 1; i <= 64; ++i){
    
25.     for(int p = 1; p <= n; ++p){
    
26.       for(int q = 1; q <= n; ++q){
    
27.         for(int r = 1; r <= n; ++r){
    
28.           if(g[p][q][i - 1] && g[q][r][i - 1]){
    
29.             g[p][r][i] = 1;
    
30.             dis[p][r] = 1;
    
31.           }
    
32.         }
    
33.       }
    
34.     }
    
35.   }
    
36.   for(int p = 1; p <= n; ++p){
    
37.     for(int i = 1; i <= n; ++i){
    
38.       for(int j = 1; j <= n; ++j){
    
39.         dis[i][j] = min(dis[i][j], dis[i][p] + dis[p][j]);
    
40.       }
    
41.     }
    
42.   }
    
43.   
    
44.   
    
45.   cout << dis[1][n] << '\n';
    
46. }
    
47. 
    
48. int main(){
    
49.   //io
    
50.   int t = 1;
    
51.   while(t--){
    
52.     sol();
    
53.   }
    
54. }
    
55. 
    

複製代碼