跑路
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-11-15JavaMailSender是什么,怎么使用?-icode9专业技术文章分享
- 2024-11-15JWT 用户校验学习:从入门到实践
- 2024-11-15Nest学习:新手入门全面指南
- 2024-11-15RestfulAPI学习:新手入门指南
- 2024-11-15Server Component学习:入门教程与实践指南
- 2024-11-15动态路由入门:新手必读指南
- 2024-11-15JWT 用户校验入门:轻松掌握JWT认证基础
- 2024-11-15Nest后端开发入门指南
- 2024-11-15Nest后端开发入门教程
- 2024-11-15RestfulAPI入门:新手快速上手指南