自动搬运

查看原文

来自洛谷，原作者为

	•́へ•́╬ Unsuccessful Leaving Something attempt

搬运于2025-08-24 22:44:42，当前版本为作者最后更新于2023-02-05 12:39:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路

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

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

建反图从终点开始跑一遍 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);
}