BFS求最短路【最少转机】

标题:

最少转机

标签:

搜索

详情:

小哼和小哈一同坐飞机去旅游，他们现在位于1号城市，目标是5号城市，可是1号城市并没有到5号城市的直航。不过小哼已经收集了很多航班的信息，现在小哼希望找到一种乘坐方式，使得转机的次数最少，如何解决呢？

输入格式:

第一行的有两个整数n m s e，n表示有n个城市（城市编号为1~n），m表示有m条航线，s表示起点城市，e表示目标城市。
接下来m行每行是一条类似“a b”这样的数据表示城市a和城市b之间有航线，也就是说城市a和城市b之间可以相互到达

输出格式:

s号城市到e号目标城市，需要飞行几次？

限制:

1<=n<=1000
1<=m<=300000

样例:

输入

5 7 1 5
1 2
1 3
2 3
2 4
3 4
3 5
4 5

输出

分析：本题也可用DFS求解，但BFS时间复杂度更低，并且BFS更适用于所有边权值相同的情况。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <queue>
#define INF 99999999
using namespace std;
const int maxn=1005;
int e[maxn][maxn];
int vis[maxn];
int minx=INF;
int n,m,s,ex;
typedef struct Node{
    int x;
    int step;
}node;
void bfs(int x){
    node p,t;
    queue<node> q;
    p.x=x;
    p.step=0;
    vis[p.x]=1;
    q.push(p);
    while(!q.empty()){
        p=q.front();
        q.pop();
        if(p.x==ex){
            if(p.step<minx){//更新最少转机次数
                minx=p.step;
            }
        }
        for(int i=1;i<=n;i++){//向x的所有邻节点扩展
            if(e[p.x][i]&&!vis[i]){
                t.x=i;
                t.step=p.step+1;
                vis[i]=1;
                q.push(t);
            }
        }
    }
}
int main()
{
    scanf("%d %d %d %d",&n,&m,&s,&ex);
    int a,b;
    for(int i=1;i<=m;i++){
        scanf("%d %d",&a,&b);
        e[a][b]=e[b][a]=1;//无向图
    }
    bfs(s);
    printf("%d
",minx);
    return 0;
}