|
本帖最後由 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 秒內跑到即可。- #include<bits/stdc++.h>
- #define ll long long
- #define INF 0x3f3f3f3f
- #define MOD 1000000007
- #define io iOS::sync_with_stdio(0);cin.tie(0);cout.tie(0);
- using namespace std;
- const int MXN = 65;
- //int ar[MXN];
- void sol(){
- ll ans = 0, n = 0, m = 0, k = 0;
- cin >> n >> m;
- int dis[MXN][MXN] = {};
- int g[MXN][MXN][MXN] = {};
- memset(dis, 10, sizeof(dis));
- for(int i = 0; i < m; ++i){
- int u, v;
- cin >> u >> v;
- dis[u][v] = 1;
- g[u][v][0] = 1;
- }
- for(int i = 1; i <= 64; ++i){
- for(int p = 1; p <= n; ++p){
- for(int q = 1; q <= n; ++q){
- for(int r = 1; r <= n; ++r){
- if(g[p][q][i - 1] && g[q][r][i - 1]){
- g[p][r][i] = 1;
- dis[p][r] = 1;
- }
- }
- }
- }
- }
- for(int p = 1; p <= n; ++p){
- for(int i = 1; i <= n; ++i){
- for(int j = 1; j <= n; ++j){
- dis[i][j] = min(dis[i][j], dis[i][p] + dis[p][j]);
- }
- }
- }
-
-
- cout << dis[1][n] << '\n';
- }
- int main(){
- //io
- int t = 1;
- while(t--){
- sol();
- }
- }
| 
發表於 2022-5-17 16:52:55
收藏
推
噓
提升卡
置頂卡
變色卡
搶沙發
千斤頂