牛客练习赛24E——青蛙

链接：https://www.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

刚开始以为是dp，d不出来，然后觉得应该是dfs，也d不出来，中间发现忘记可以往回走这种情况还一度以为能过，结果发现这不就是一个0到m的最短路嘛，直接dijkstra模板抄一抄，改一改，就过了……

代码：

#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
const int MAXN=1010;
const int INF=0x3f3f3f3f;
bool vis[MAXN];
int cost[MAXN][MAXN];
int lowcost[MAXN];
int n;
int m;
int u,v,c;
int s,e;
void Dijkstra(int s){
    for(int i=0;i<=n;i++){
        lowcost[i]=INF;
        vis[i]=false;
    }
    lowcost[s]=0;
    for(int i=0;i<=n;i++){
        int k=-1;
        int Min=INF;
        for(int j=0;j<=n;j++){
            if(!vis[j] && lowcost[j]<Min){
                Min=lowcost[j];
                k=j;
            }
        }
        if(k==-1){
            break;
        }
        vis[k]=true;
        for(int j=0;j<=n;j++){
            if(!vis[j] && lowcost[k]+cost[k][j]<lowcost[j]){
                lowcost[j]=lowcost[k]+cost[k][j];
            }
        }
    }
}
int main(void){
    scanf("%d%d",&n,&m);
    memset(cost,INF,sizeof(cost));
    for(int i=0;i<m;i++){
        scanf("%d%d",&u,&v);
        cost[u][v]=1;
    }
    for(int i=0;i<n;i++){
        cost[i][i+1]=1;
        cost[i+1][i]=1;
    }
    Dijkstra(0);
    printf("%d\n",lowcost[n]);
    return 0;
}