跑路
2022/8/28 23:53:49
本文主要是介绍跑路,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
P1613 跑路 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- 题意:如果两点之间有边连接那么边为1,然后如果两点之间有2^n长度的路径,那么他们距离就变为1
- dp数组标记i到j有无2^p的距离的边,如果有,其dis值更新为1
- 第一次floyd如果i到k有距离p-1,k到j有距离p-1的边,那么他们就有距离p的边,通过k中转
- 最后再floyd求最短路
#include <bits/stdc++.h> using namespace std; #define N 60 #define INF 2e9 // https://www.luogu.com.cn/problem/P1613 int n, m; bool dp[N][N][100]; int dis[N][N]; int main() { cin >> n >> m; memset(dis, 0x3f, sizeof(dis)); for (int i = 1, u, v; i <= m; i++) scanf("%d%d", &u, &v), dp[u][v][0] = true, dis[u][v] = 1; for (int p = 1; p <= 65; p++) for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) if (dp[i][k][p - 1] && dp[k][j][p - 1]) dp[i][j][p] = true, dis[i][j] = 1; for (int k = 1; k <= n; k++) for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]); printf("%d", dis[1][n]); }
这篇关于跑路的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?
- 2024-05-09企业src漏洞挖掘-有意思的命令执行