冰楓論壇

 找回密碼
 立即註冊
搜索
查看: 1046|回覆: 0

[心得] [演算法心得] luogu 跑路

[複製鏈接]

7

主題

0

好友

11

積分

新手上路

Rank: 1

UID
320966
帖子
146
主題
7
精華
0
積分
11
楓幣
756
威望
11
存款
0
贊助金額
0
推廣
0
GP
31
閱讀權限
10
性別
保密
在線時間
9 小時
註冊時間
2021-9-30
最後登入
2022-7-6
發表於 2022-5-17 16:52:55 |顯示全部樓層
本帖最後由 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;

  8. //int ar[MXN];

  9. void sol(){
  10.   ll ans = 0, n = 0, m = 0, k = 0;

  11.   cin >> n >> m;
  12.   int dis[MXN][MXN] = {};
  13.   int g[MXN][MXN][MXN] = {};
  14.   memset(dis, 10, sizeof(dis));
  15.   for(int i = 0; i < m; ++i){
  16.     int u, v;
  17.     cin >> u >> v;
  18.     dis[u][v] = 1;
  19.     g[u][v][0] = 1;
  20.   }
  21.   for(int i = 1; i <= 64; ++i){
  22.     for(int p = 1; p <= n; ++p){
  23.       for(int q = 1; q <= n; ++q){
  24.         for(int r = 1; r <= n; ++r){
  25.           if(g[p][q][i - 1] && g[q][r][i - 1]){
  26.             g[p][r][i] = 1;
  27.             dis[p][r] = 1;
  28.           }
  29.         }
  30.       }
  31.     }
  32.   }
  33.   for(int p = 1; p <= n; ++p){
  34.     for(int i = 1; i <= n; ++i){
  35.       for(int j = 1; j <= n; ++j){
  36.         dis[i][j] = min(dis[i][j], dis[i][p] + dis[p][j]);
  37.       }
  38.     }
  39.   }
  40.   
  41.   
  42.   cout << dis[1][n] << '\n';
  43. }

  44. int main(){
  45.   //io
  46.   int t = 1;
  47.   while(t--){
  48.     sol();
  49.   }
  50. }

複製代碼
複製連結並發給好友,以賺取推廣點數
簡單兩步驟,註冊、分享網址,即可獲得獎勵! 一起推廣文章換商品、賺$$
高級模式
B Color Image Link Quote Code Smilies |上傳

廣告刊登意見回饋關於我們管群招募本站規範DMCA隱私權政策

Copyright © 2011-2024 冰楓論壇, All rights reserved

免責聲明:本網站是以即時上載留言的方式運作,本站對所有留言的真實性、完整性及立場等,不負任何法律責任。

而一切留言之言論只代表留言者個人意見,並非本網站之立場,用戶不應信賴內容,並應自行判斷內容之真實性。

小黑屋|手機版|冰楓論壇

GMT+8, 2024-6-19 00:17

回頂部