题解：P9026 [CCC2021 S4] Daily Commute

· · 题解

这道题的思路特别难想。\ 首先，考虑路径方案。

  1. 先走路又坐地铁。这样会等地铁，对不对，就会导致时间拖延。
  2. 先做地铁又走路。这样可以一开始就坐地铁，不会有任何拖延。

接下来因为地铁会有改动，走路不会改动，所以走路可以预处理好，记得建反图。\ 后面地铁的用个优先队列维护，记住这个地点和编号，到后面看看还是不是，如果是，那么中转点就是他。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+1;
int n,m,k,op[N],dist[N];
bool ok[N];
queue<int> q;
struct ANS{
    int pos,id;
    bool operator<(const ANS &x) const{
        return pos-1+dist[id]>x.pos-1+dist[x.id];
    }
};
priority_queue<ANS> pq;
vector<int> g[N];
signed main(){
    scanf("%lld%lld%lld",&n,&m,&k);
    for(int i=1; i<=m; ++i){
        int u,v;
        scanf("%lld%lld",&u,&v);
        g[v].push_back(u);
    }
    for(int i=1; i<=n; ++i){
        dist[i]=1e9;
        ok[i]=false;
    }
    q.push(n);
    ok[n]=true;
    dist[n]=0;
    while(q.size()){
        int u=q.front();
        q.pop();
        for(int i=0; i<g[u].size(); ++i){
            if(dist[u]+1<dist[g[u][i]]){
                dist[g[u][i]]=dist[u]+1;
                ok[g[u][i]]=true;
                q.push(g[u][i]);
            }
        }
    }
    for(int i=1; i<=n; ++i){
        scanf("%lld",&op[i]);
        pq.push({i,op[i]});
    }
    while(k--){
        int u,v;
        scanf("%lld%lld",&u,&v);
        swap(op[u],op[v]);
        pq.push({u,op[u]});
        pq.push({v,op[v]});
        while(op[pq.top().pos]!=pq.top().id)pq.pop();
        ANS x=pq.top();
        printf("%lld\n",x.pos-1+dist[x.id]);
    }
    return 0;
}