企业网站的设计,企业网站系统模板,苏州网站制作搭建,设计房子的软件免费题干#xff1a;
链接#xff1a;https://ac.nowcoder.com/acm/contest/157/E 来源#xff1a;牛客网
题目描述
有一只可爱的老青蛙#xff0c;在路的另一端发现了一个黑的东西#xff0c;想过去一探究竟。于是便开始踏上了旅途
一直这个小路上有很多的隧道#xff0…题干
链接https://ac.nowcoder.com/acm/contest/157/E 来源牛客网
题目描述
有一只可爱的老青蛙在路的另一端发现了一个黑的东西想过去一探究竟。于是便开始踏上了旅途
一直这个小路上有很多的隧道从隧道的a进入会从b出来但是隧道不可以反向走。
这只青蛙因为太老了所以很懒现在想请你帮帮慢问他最少需要几步才可以到达对面。
将小径看作一条数轴青蛙初始在0上这只青蛙可以向前跳也可以向后跳但每次只能跳一格每跳一格记作一步从隧道进到隧道出算做一步。
输入描述:
第一行两个数m,n表示黑色物品在数轴m点上数轴上总共有n个隧道
接下来n行每行ab两个数表示从a进会从b出10 m,n 2330a,bm
输出描述:
一个数ans表示最小步数
示例1
输入
复制
16 4
2 10
8 15
12 5
13 6
输出
复制
7
说明 0--1--2--10--9--8--15--16 解题报告 建图跑floyd就可以了。
AC代码
#includecstdio
#includeiostream
#includealgorithm
#includequeue
#includemap
#includevector
#includeset
#includestring
#includecmath
#includecstring
#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; kn; k) {for(int i 0; in; i) {for(int j 0; jn; j) {dis[i][j] min(dis[i][j],dis[i][k] dis[k][j]);}}}
}
int main()
{cinnm;memset(dis,0x3f,sizeof dis);for(int a,b,i 1; im; i) {scanf(%d%d,a,b);dis[a][b] 1;}for(int i 1; in; i) {dis[i][i-1] dis[i-1][i] 1;}floyd();printf(%d\n,dis[0][n]);return 0 ;
}
