AcWing 342. 道路与航线（SLF优化下的Spfa）

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 342. 道路与航线（SLF优化下的Spfa）原题链接中等

作者：

氟锑磺酸 , 2021-03-09 20:34:15 , 所有人可见 , 阅读 1418

7

3

道路与航线

技巧：SLF优化下的Spfa

本题相比于最传统的负环最短路问题，存在了两个问题：
1.能够卡传统的spfa，导致TLE 《— $一般情况下spfa的时间复杂度为O(m),而最极端情况下为O(nm)$
2.本题存在已经插入邻接表但是不能使用的边

为了解决第一个问题，采用了SLF优化下的spfa算法，那么什么是SLF优化呢？

对于传统手艺的spfa，采用的更新策略是，不管三七二十一都插入到队列的尾部，这也就是优化所在了，伪代码如下：

如果当前要入队的节点的距离 > 当前未出队的队头的距离
    将节点从后方入队
否则
    将节点从前方入队

为了实现上述伪代码，就需要使用到$deque$数据结构，而不再是$queue$了

解决了第二个问题，那么要怎么处理失效的边呢？

我采取的策略是，另开一个邻接表专门存储失效边的信息，然后在spfa每轮遍历当前队头元素的链的时候，先判断两两节点之间是否还存在有效路径，如果存在则更新，反之忽略。

#include <iostream>
#include <queue>
#include <cstring>

using namespace std;

typedef pair<int,int> PII;

const int N = 1e6 + 10;
int h[N],e[N],ne[N],w[N],idx;
int h1[N],e1[N],ne1[N],idx1;
int dist[N];
bool v[N];

//T代表总城镇个数，R代表道路总数，P代表航线总数，S代表牛奶中心下标
int T,R,P,S;

//判断a,b之间的道路是否被政策影响
bool isValid(int a,int b)
{
    for(int i = h1[a]; i != -1; i = ne1[i])
    {
        if(e1[i] == b)
            return false;
    }
    return true;
}

//构建邻接表
void add(int a,int b,int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++;
}

//构建无效信息邻接表
void add1(int a,int b)
{
    e1[idx1] = b, ne1[idx1] = h1[a], h1[a] = idx1 ++;
}

void spfa()
{
    memset(dist, 0x3f, sizeof dist);
    deque<int> q;
    q.push_back(S);
    dist[S] = 0;
    v[S] = true;

    while(q.size())
    {
        int t = q.front();
        q.pop_front();

        v[t] = false;
        for(int i = h[t]; i != -1; i = ne[i])
        {
            int j = e[i];
            if(isValid(t,j) && dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if(!v[j])
                {
                    v[j] = true;
                    if(q.size() && dist[j] < dist[q.front()])
                        q.push_front(j);
                    else
                        q.push_back(j);
                }
            }
        }
    }
    return ;
}

int main()
{
    memset(h, -1, sizeof h);
    memset(h1, -1, sizeof h1);
    scanf("%d%d%d%d",&T,&R,&P,&S);

    for(int i = 0; i < R; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        add(b,a,c);
    }

    for(int i = 0; i < P; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d",&a,&b,&c);
        add(a,b,c);
        //记录相反的点不构成航线和道路
        add1(b,a);
    }

    spfa();

    for(int i = 1; i <= T; i ++ )
    {
        if(dist[i] > 0x3f3f3f3f / 2)    puts("NO PATH");
        else    cout<<dist[i]<<endl;
    }
    return 0;
}

5 评论

wyf_sinon 8个月前

原来这个政策是说不让你回去吗我还以为是保证没有负环

9年级的蒟蒻 2023-01-03 15:52

为什么要check?你在想什么？

KobeBryant24 2022-03-24 20:09

#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#define x first
#define y second

using namespace std;
typedef pair<int, int> PII;
const int N = 25010;
int dis[N];
bool st[N];
vector<PII> G[N];
vector<int> changed[N];
int t, r, p, s;

bool check(int from, int to){
    for(auto isChanged : changed[from])
        if(isChanged == to)
            return false;
    return true;
}

void spfa(int start){
    memset(dis, 0x3f, sizeof dis);
    deque<int> myDeque;
    myDeque.push_back(start);
    dis[start] = 0;
    st[start] = true;
    while(myDeque.size()){
        auto t = myDeque.front();
        myDeque.pop_front();
        st[t] = false;
        for(auto next : G[t]){
            int nextId = next.y, distance = next.x;
            if(check(t, nextId) && dis[nextId] > dis[t] + distance){
                dis[nextId] = dis[t] + distance;
                if(!st[nextId] && dis[nextId] > dis[myDeque.front()]){
                    st[nextId] = true;
                    myDeque.push_back(nextId);
                }else if(!st[nextId] && dis[nextId] <= dis[myDeque.front()]){
                    st[nextId] = true;
                    myDeque.push_front(nextId);
                }
            }
        }
    }

}

/* queue 版本 14/16
// 但是感觉是不是数据没加强的原因，由于题目中写了航线会导致陆地路线的改变我这里没有判断是否该边 
// 还需要另外加一个邻接链表来判断 是否受到了影响
void spfa(int start){
    memset(dis, 0x3f, sizeof dis);
    dis[start] = 0;
    queue<int> myQueue;
    myQueue.push(start);
    st[start] = true;
    while(myQueue.size()){
        int t = myQueue.front();
        myQueue.pop();
        st[t] = false;
        for(auto next : G[t]){
            int nextId = next.y, distance = next.x;
            if(dis[nextId] > dis[t] + distance){
                dis[nextId] = dis[t] + distance;
                if(!st[nextId]){
                    st[nextId] = true;
                    myQueue.push(nextId);
                }
            }
        }
    }
}
*/
int main(){
    cin >> t >> r >> p >> s;
    while(r--){
        int x, y, z;
        cin >> x >> y >> z;
        G[x].push_back({z, y}), G[y].push_back({z, x});
    }
    while(p--){
        int x, y, z;
        cin >> x >> y >> z;
        G[x].push_back({z, y});
        changed[y].push_back(x);
    }
    spfa(s);
    for(int i = 1; i <= t; ++i){
        if(dis[i] == 0x3f3f3f3f)    puts("NO PATH");
        else cout << dis[i] << endl;
    }
    return 0;
}

这样写也会被卡…好像是check里的vector 不知道为啥

可达duck 2022-01-12 20:37

$\color{blue}{SLF优化那里，插入方向写反了吧}$

氟锑磺酸 2022-01-14 15:55

啊对，是写反了，蟹蟹指正！

App 内打开