题目链接：https://www.nowcoder.com/acm/contest/157/E

       这道题其实就是求从0到n的最短路，可以用最dij去写，就是初始化的时候需要点改动，剩下的就是模板。用dij写完以后我感觉还能用bfs去写，能走的路都设为1，不能走的都设为0或-1就好了，然后跑一遍bfs，试着交了一发，果然bfs可写...

AC代码(dijkstra)：

#include <iostream>
#include <cstring>
#include <cstdio>
#define maxn 235
#define inf 0x3f3f3f3f
using namespace std;
int n,m;
int pre[maxn][maxn];
 
void init(){
    memset(pre,inf,sizeof(pre));
    for(int i=0;i<n;i++){
        pre[i][i+1] = 1;
        pre[i+1][i] = 1;
    }
}
 
void dijkstra(){
    int Min,flag;
    bool vis[maxn];
    int dis[maxn];
    for(int i=0;i<=n;i++){
        dis[i] = pre[0][i];
        vis[i] = 0;
    }
    for(int i=0;i<=n;i++){
        Min = inf;
        for(int j=0;j<=n;j++){
            if(!vis[j] && dis[j] < Min){
                Min = dis[j];
                flag = j;
            }
        }
        vis[flag] = 1;
        for(int j=0;j<=n;j++){
            if(!vis[j] && dis[j] > dis[flag] + pre[flag][j]){
                dis[j] = dis[flag] + pre[flag][j];
            }
        }
    }
    printf("%d\n",dis[n]);
}
 
int main()
{
    scanf("%d%d",&n,&m);
    init();
    for(int i=0;i<m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        pre[u][v] = 1;
    }
    dijkstra();
    return 0;
}

AC代码(bfs)：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#define maxn 235
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
    int x,step;
}Now,Next,S,E;
int n,m;
int pre[maxn][maxn];
 
void init(){
    memset(pre,-1,sizeof(pre));
    for(int i=0;i<n;i++){
        pre[i][i+1] = 1;
        pre[i+1][i] = 1;
    }
}
 
int bfs(){
    queue<Node> q;
    S.x = 0;
    S.step = 0;
    q.push(S);
    while(!q.empty()){
        Now = q.front();
        q.pop();
        if(Now.x == n){
            return Now.step;
        }
        for(int i=0;i<=n;i++){
            if(pre[Now.x][i] == 1){
                pre[Now.x][i] = -1;
                Next.x = i;
                Next.step = Now.step + 1;
                q.push(Next);
            }
        }
    }
    return -1;
}
 
int main()
{
    scanf("%d%d",&n,&m);
    init();
    for(int i=0;i<m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        pre[u][v] = 1;
    }
    printf("%d\n",bfs());
    return 0;
}