单源最短路之01BFS

荼白 · 2020-11-28 16:40:18 · 个人记录

学习源泉:https://codeforces.com/blog/entry/22276

例题:P1346

应用场景

有一个加权图，但是边权有一个限制，它们只能是0或1，求开始结点到结束结点的最短路。

优势

时间复杂度为O（E + V），它是线性的，并且比Dijkstra(优化版)更有效。

步骤

• 将到所有点的距离赋为 INF

• 将到源点的距离赋为 0

• 将源点的标号入队

1. 取出队头点u,遍历其能访问到的各个点v

2. 看看该点能否进行松弛操作

   • 如果能松弛

     • 边权为0丢队头,边权为1丢队尾

   • 如果不能松弛,换边

• 重复1、2直到队列为空

例题Code

#include <iostream>
#include <cstring>
#include <queue>
#include <climits>
#include <algorithm>
using namespace std;
const int N = 1e4;
struct Edge{
    int val;
    int to;
    int next;
}e[N];
int dis[N];
int head[N];
bool vis[N];
int cnt;
inline void add(int u,int v,int w){
    cnt++;
    e[cnt].to=v;
    e[cnt].val=w;
    e[cnt].next=head[u];
    head[u]=cnt;
}
const int INF = (1<<29);
deque<int> dq;//放结点
int main()
{
    int n,s,t;
    cin >> n >> s >> t;
    int k;
    for(int i=1;i<=n;i++){
        cin >> k;
        for(int j=1,to;j<=k;j++){
            cin >> to;
            if(j==1){
                add(i,to,0);
            }else{
                add(i,to,1);
            }
        }
    }
    dq.push_front(s);
    fill(dis+1,dis+1+n,INF);
    dis[s]=0;
    while(!dq.empty()){
        int u = dq.front();
        dq.pop_front();
        //每个点只用访问一次
        //因为我们先拿到的一定是为'0'的点
        //直到为'0'的点松弛完毕 才轮到为1的点
        //因为我们要求最短路
        //用为0的点松弛完一些点后
        //再用为1的点跑bfs显然是正确的
        if(vis[u]) continue;
        vis[u]=1;
        for(int i=head[u];i;i=e[i].next){
            int to = e[i].to;
            int val = e[i].val;
            if(dis[to]>dis[u]+val){
                dis[to]=dis[u]+val;
                if(val){
                    dq.push_back(to);
                }else{
                    dq.push_front(to);
                }
            }
        }
    }
    cout << (dis[t]==INF?-1:dis[t]);
    return 0;
}