【牛客 - 157E】青蛙（floyd最短路，建图）

题干：

链接：https://ac.nowcoder.com/acm/contest/157/E
来源：牛客网

题目描述

有一只可爱的老青蛙，在路的另一端发现了一个黑的东西，想过去一探究竟。于是便开始踏上了旅途

一直这个小路上有很多的隧道，从隧道的a进入，会从b出来，但是隧道不可以反向走。

这只青蛙因为太老了，所以很懒，现在想请你帮帮慢，问他最少需要几步才可以到达对面。

将小径看作一条数轴，青蛙初始在0上，这只青蛙可以向前跳也可以向后跳，但每次只能跳一格，每跳一格记作一步，从隧道进到隧道出算做一步。

输入描述:

第一行两个数m,n；表示黑色物品在数轴m点上，数轴上总共有n个隧道 接下来n行，每行a，b两个数，表示从a进会从b出10 <= m,n <= 2330<a,b<=m

输出描述:

一个数ans表示最小步数

示例1

输入

复制

16 4 2 10 8 15 12 5 13 6

输出

复制

7

说明

 

0-->1-->2-->10-->9-->8-->15-->16

解题报告：

   建图跑floyd就可以了。

AC代码：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define ll long long #define pb push_back #define pm make_pair using namespace std; const int MAX = 2e5 + 5; int n,m; int dis[555][555]; void floyd() {for(int k = 0; k<=n; k++) {for(int i = 0; i<=n; i++) {for(int j = 0; j<=n; j++) {dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);}}} } int main() {cin>>n>>m;memset(dis,0x3f,sizeof dis);for(int a,b,i = 1; i<=m; i++) {scanf("%d%d",&a,&b);dis[a][b] = 1;}for(int i = 1; i<=n; i++) {dis[i][i-1] = dis[i-1][i] = 1;}floyd();printf("%d\n",dis[0][n]);return 0 ; }

 

总结

以上是生活随笔为你收集整理的【牛客 - 157E】青蛙（floyd最短路，建图）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。