自动搬运

查看原文

来自洛谷，原作者为

	Unordered_OIer **

搬运于2025-08-24 22:31:51，当前版本为作者最后更新于2021-06-25 22:24:47，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

P7646 题解

Description

一根超级管道能够将 $K$ 个站台连接在一起。求从站台 $1$ 到达站台 $N$ 最少需要经过多少个站台。

Solution

最短路裸题。

考虑将一根所谓的 $m$ 个“超级管道”变成 $m$ 个连接了 $k$ 个点的点，那么转化之后就是裸的最短路问题了。

看到目前为止其他两篇题解讲的答案需要 dis[n]/2+1 都不是很清楚，这里再讲一遍：

先看一下一个“超级管道”连接 $2$ 个点的情况，根据题意我们显然可以看作：

但是，照着我们的思路，我们会把它变成：

原本 $1 \rightarrow 2$ 的路径会被拆成 $1 \rightarrow 3 \rightarrow 2$，也就是说我们求出的最短路径实际上是原来的 $2$ 倍。如果把 $1 \rightarrow n$ 的最短路记作 $dis[n]$，那么原来的最短路径就是 $\dfrac{dis[n]}{2}$。

因为要求的是点数，所以答案是 $\dfrac{dis[n]}{2}+1$。

最后的话这题卡空间不能开 long long，开了 long long 你就会和我一样提交了若干遍最后两个点 $\color{white}\colorbox{#052242}{MLE}$。

Code

inline void bfs(){
	memset(dst,-1,sizeof dst);
	queue<int> q;dst[1]=1;
	q.push(1);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(int i=hd[u];i;i=es[i].nxt){
			int v=es[i].to;
			if(dst[v]==-1){
				dst[v]=dst[u]+1;
				q.push(v);
			}
		}
	}
}
int main(){
	n=read(),k=read(),m=read();
	for(int i=1;i<=m;i++)
		for(int j=1;j<=k;j++){
			int x=read();
			add(n+i,x),add(x,n+i);
		}
	bfs();
	writeln(dst[n]==-1?-1:dst[n]/2+1);
	return 0;
}