【牛客 - 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 <= 233

0<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 ;
}