思路
每条边的权重都是相同的正数,可以用bfs来求最短距离。
-
y总:开辟一个距离数组d,让每个第一次被访问到的节点记录当前的层数(即一号到自己的最短距离),最后,返回d[n]
-
变化:我只维护一个当前层数,每次都把队列里的所有元素(即上一层的)取出,层数加加。注意,中间遇到n就直接返回当前层数加一。
- 由于存在提前返回的情况,速度快一点。为了省劲儿我用了vector表示邻接表,数组描述应该可以更快。
my c++
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define ffor(i,s,e) for(int i=s;i<e;i++)
#define out(x) cout<<x<<" "
#define nl cout<<endl
const int N = 100010,M=100010,INF=0x3f3f3f3f;
int n,m;
vector<int> adj[N];
int vis[N];
void init(){
cin>>n>>m;
ffor(i,0,m){
int a,b;
scanf("%d%d",&a,&b);
adj[a].push_back(b);
}
/*test
ffor(i,1,n+1){
out(i);out("->");
for(auto &x: adj[i]) out(x);
nl;
}
*/
}
bool pushNxt(int now,queue<int> &que){
bool over=false;
for(auto &x:adj[now]){
if(x==n){
over=true;
break;
}
if(!vis[x]){
vis[x]=1;
que.push(x);
}
}
return over;
}
int bfs(int s){
int steps=0;
vis[s]=1;
queue<int> que;
que.push(s);
while(que.size()){
//当前now--end_即上一层的全部元素
int now=que.front();que.pop();
int end_=que.back();
while(now!=end_){
if(pushNxt(now,que)) return steps+1 ;
now=que.front();que.pop();
}
if(pushNxt(now,que)) return steps+1 ;
//处理完上一层
steps++;
}
return -1;
}
void acwing(){
init();
out(bfs(1));nl;
}
int main(){
// init();
acwing();
return 0;
}
y总
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int d[N];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
int bfs()
{
memset(d, -1, sizeof d);
queue<int> q;
d[1] = 0;
q.push(1);
while (q.size())
{
int t = q.front();
q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (d[j] == -1)
{
//第一次访问到,比父亲的层数加一
d[j] = d[t] + 1;
q.push(j);
}
}
}
return d[n];
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof h);
for (int i = 0; i < m; i ++ )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
cout << bfs() << endl;
return 0;
}