冰楓論壇

標題: [演算法心得] luogu 跑路 [打印本頁]
作者: jimmyhealer    時間: 2022-5-17 16:52
標題: [演算法心得] luogu 跑路
本帖最後由 jimmyhealer 於 2022-5-17 16:54 編輯

嗨大家好~ 我是新加入論壇的萌新，之後可能會每日更新一下演算法心得，那目前會在 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;

  9. //int ar[MXN];

  11. void sol(){
  12.   ll ans = 0, n = 0, m = 0, k = 0;

  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. }

  48. int main(){
  49.   //io
  50.   int t = 1;
  51.   while(t--){
  52.     sol();
  53.   }
  54. }

複製代碼




歡迎光臨 冰楓論壇 (https://bingfong.com/) Powered by 冰楓