题干:

链接: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 ;
}