跑路
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-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门:从零开始的编程之旅
- 2024-11-23Java创业入门:新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门:初学者的简单教程
- 2024-11-23JAVA副业入门:初学者的实战指南