链接：https://www.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表示最小步数
输入
16 4
2 10
8 15
12 5
13 6
输出
7 提示：
0-->1-->2-->10-->9-->8-->15-->16
题解：一看题目，我就想用BFS做，但是最后却卡在了一个细节上，就是在写check函数的时候，0<a&&a<=n被我写成0<a<=n，这个真的下次得注意了！
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mod 1000000007
#define INF 0x3f3f3f3f
const int N=;
int n,m;
vector<int>s[N];
int ans=INF;
int vis[N][N];
int d[N];
struct niu
{
int x;
int step;
niu(){}
niu(int xt,int st)
{
x=xt,step=st;
}
};
queue<niu>q;
bool check(int a){return <a&&a<=n;}//注意这里不能写成0<a<=n;
void bfs()
{
while(q.size())q.pop();
memset(vis,,sizeof(vis));
q.push(niu(,));
vis[][]=;
while(q.size())
{
niu tmp=q.front();
q.pop();
if(tmp.x==n){
ans=min(ans,tmp.step);
return ;
}
for(int nx: s[tmp.x])
{
if(check(nx)&&vis[nx][tmp.step]==)
{
vis[nx][tmp.step]=;
q.push(niu(nx,tmp.step+)); }
}
int ny=tmp.x+;
if(check(ny)&&vis[ny][tmp.step]==)
{
vis[ny][tmp.step]=;
q.push(niu(ny,tmp.step+)); }
int nz=tmp.x-;
if(check(nz)&&vis[nz][tmp.step]==)
{
vis[nz][tmp.step]=;
q.push(niu(nz,tmp.step+)); }
}
}
int main()
{;
ios_base::sync_with_stdio(); cin.tie();
cin>>n>>m;
int a,b;
for(int i=;i<m;i++)
{
cin>>a>>b;
s[a].push_back(b);
}
/* for(int i=0;i<=n;i++)
for(int j: s[i])
cout<<j<<endl;*/
bfs();
cout<<ans<<endl;
return ;
}
这道题也可以用最短路floyed算法做(这种做法我又犯了一个错误，n,m定义全局变量后，又在下面定义成局部变量，这使得调用floyed函数时出错）
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define mod 1000000007
#define INF 0x3f3f3f3f
const int N=;
int n,m;
int d[N][N];
void floyed()
{
for(int k=;k<=n;k++)
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
}
int main()
{ //这里不能在定义一次n,m
ios_base::sync_with_stdio();
cin.tie();
cin>>n>>m;
memset(d,INF,sizeof(d));
for(int i=;i<m;i++)
{
int a,b;
cin>>a>>b;
d[a][b]=;
}
for(int i=;i<=n;i++)
{
d[i][i-]=;
d[i-][i]=;
d[i][i]=;
}
floyed();
cout<<d[][n]<<endl;
return ;
}