题解：P9026 [CCC2021 S4] Daily Commute

P9026 [CCC2021 S4] Daily Commute 题解

传送门

在这道题中，比普通的最短路题还要多了一个地铁，所以我们重点来考虑这个地铁。

如题，地铁只有一趟，所以我们可以选择坐或者不坐，也可以是中途下车，而不会中途上车。如果你比地铁先一步到达地铁站，还是要等待地铁，所以和一开始就上地铁的时间是一样的，所以坐地铁就只会有三种情况。

然后我们还需要求出每个点到终点的距离，不要每一次都重新求，那样时间复杂度会有点高，边权都为1，我们可以使用广搜求最短路，由于我们不好以每个点为起点，然后往 n 走，我们可以以 n 为起点，建立反边跑广搜。然后再交换后枚举在哪一个时刻下车，再加上 dis_{s_i} - 1。这样我们就可以得到 90 分了，毕竟也是道绿题，不可能这么简单就得到满分的，我先把这份暴力代码放一下。

#include<bits/stdc++.h>
using namespace std;
int n,m,q;
int dis[200005];
vector<int>g[200005];
int s[200005]; 
void bfs(){//跑遍最短路
    for(int i=1;i<n;i++){//初始化
        dis[i]=2e9;
    }
    queue<int>q;
    q.push(n);
    while(q.size()){
        int u=q.front();
        q.pop();
        for(auto v:g[u]){
            if(dis[v]==2e9){
                q.push(v);
                dis[v]=dis[u]+1; 
            }
        } 
    }
    return;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    bfs();
    for(int i=1;i<=q;i++){
        int x,y;
        cin>>x>>y;
        swap(s[x],s[y]);
        int minn=2e9;
        for(int j=1;j<=n;j++){//枚举下车时刻
            minn=min(minn,dis[s[j]]+j-1);
        }
        cout<<minn<<"\n";
    }
    return 0;
}

然后我们就需要对这份代码进行优化了，枚举的时间复杂度是 O(qn) 所以我们需要优化。

最优，看到这两个字，就让人想到了优先队列，我们可以先把没有任何交换过的答案放进优先队列，每次交换后把在 s_x 与 s_y 的位置下车重新放进队列，这时我们发现无法删除，但是我们没必要把对答案没有影响的答案排出去，所以我们从头开始判断。我们的优先队列记录两个值第几站，是到达那个点，然后我们判断优先队列的头如果和我们先在的 s 数组对不上号，就把它踢掉，由于会有多个，此过程使用 while 循环。

正确代码

#include<bits/stdc++.h>
#include<vector>
using namespace std;
int n,m,f;
int dis[200005];
vector<int>g[200005];
int s[200005];
void bfs(){
    for(int i=1;i<n;i++){
        dis[i]=2e9;
    }
    queue<int>q;
    q.push(n);
    while(q.size()){
        int u=q.front();
        q.pop();
        for(auto v:g[u]){
            if(dis[v]==2e9){
                q.push(v);
                dis[v]=dis[u]+1; 
            }
        } 
    }
    return;
}
struct no{
    int pos,id;
    bool operator<(const no&x)const
    {
        return pos-1+dis[id]>x.pos-1+dis[x.id];
    }
};
priority_queue<no>q;
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>f;
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;
        g[v].push_back(u);
    }
    for(int i=1;i<=n;i++){
        cin>>s[i];
    }
    bfs();
    for(int i=1;i<=n;i++){
        q.push({i,s[i]});
    }
    for(int i=1;i<=f;i++){
        int x,y;
        cin>>x>>y;
        swap(s[x],s[y]);
        q.push({x,s[x]});
        q.push({y,s[y]});
        while(s[q.top().pos]!=q.top().id){//将对不上号的给踢出去
            q.pop();
        }
        cout<<q.top().pos-1+dis[q.top().id]<<"\n";
    }
    return 0;
}

十年洛谷一场空，复制题解名变棕。