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