P9026 [CCC2021 S4] Daily Commute 题解

· · 题解

思路

最优方案一定是只从起点开始坐一段地铁。

因为，如果你坐两段，还会存在等地铁这种事情，一定不会更优。

建反图从终点开始跑一遍 bfs，得到每个点到终点的距离。

每个点到起点的距离就是 S 的逆排列。逆排列就是把下标和数值换一下，我代码里记做 a。

两个拼起来，取最小值就是答案。

因为有修改，用数据结构维护一下。

code

用 set 实现，跑的很慢。

#include<stdio.h>
#include<deque>
#include<set>
#define N 222222
#define pr pair<int,int> 
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,m,d,s[N],a[N],h[N],e[N],nxt[N],dis[N];set<pr>qwq;
deque<int>q;
main()
{
    read(n);read(m);read(d);
    for(int i=1,u,v;i<=m;++i)read(u),read(v),--u,--v,
        e[i]=u,nxt[i]=h[v],h[v]=i;
    for(int i=0,x;i<n;read(s[i]),a[--s[i]]=i,dis[i++]=1<<30);
    q.emplace_back(n-1);dis[n-1]=0;
    for(int i;q.size();)
    {
        i=q.front();q.pop_front();
        for(int j=h[i];j;j=nxt[j])if(dis[e[j]]>>30)
            dis[e[j]]=dis[i]+1,q.emplace_back(e[j]);
    }
    for(int i=0;i<n;++i)qwq.emplace(dis[i]+a[i],i);
    for(int u,v;d--;printf("%d\n",qwq.begin()->first))
    {
        read(u);read(v);--u;--v;
        swap(s[u],s[v]);
        u=s[u];v=s[v];
        qwq.erase((pr){dis[u]+a[u],u});qwq.erase((pr){dis[v]+a[v],v});
        swap(a[u],a[v]);
        qwq.emplace(dis[u]+a[u],u);qwq.emplace(dis[v]+a[v],v);
    }
}

code

用堆实现，跑的很快。

#include<stdio.h>
#include<queue>
#define N 222222
#define pr pair<int,int> 
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
inline void pc(const char&c)
{
    static char buf[99999],*r=buf;
    (!c||(*r++=c,r==buf+99999))&&(fwrite(buf,1,r-buf,stdout),r=buf);
}
inline void pi(const int&x){if(x>9)pi(x/10);pc(x%10+'0');}
int n,m,d,s[N],a[N],h[N],e[N],nxt[N],dis[N];
priority_queue<pr,vector<pr>,greater<pr> >qwq;deque<int>q;
main()
{
    read(n);read(m);read(d);
    for(int i=1,u,v;i<=m;++i)read(u),read(v),--u,--v,
        e[i]=u,nxt[i]=h[v],h[v]=i;
    for(int i=0,x;i<n;read(s[i]),a[--s[i]]=i,dis[i++]=1<<30);
    q.emplace_back(n-1);dis[n-1]=0;
    for(int i;q.size();)
    {
        i=q.front();q.pop_front();
        for(int j=h[i];j;j=nxt[j])if(dis[e[j]]>>30)
            dis[e[j]]=dis[i]+1,q.emplace_back(e[j]);
    }
    for(int i=0;i<n;++i)qwq.emplace(dis[i]+a[i],i);
    for(int u,v;d--;pi(qwq.top().first),pc('\n'))
    {
        read(u);read(v);--u;--v;
        swap(s[u],s[v]);
        u=s[u];v=s[v];
        swap(a[u],a[v]);
        qwq.emplace(dis[u]+a[u],u);qwq.emplace(dis[v]+a[v],v);
        for(;qwq.top().first^dis[qwq.top().second]+a[qwq.top().second];
            qwq.pop());
    }
    pc(0);
}