自动搬运

查看原文

来自洛谷，原作者为

	Lovely_Chtholly **

搬运于2025-08-24 22:37:54，当前版本为作者最后更新于2023-03-23 13:25:51，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

本蒟蒻的第一篇题解，如有错误请大家悉心指出。

个人博客食用效果更佳

题目传送门

【分析】

其实这道题就是给你一个有 $n$ 个点，$m$ 条边，$m$ 条路的有向图，再根据 $q$ 次询问输出从 $c_i$ 到 $d_i$ 的最短路长度。

前置芝士

我们来看一张图：

经过分析，我们发现本题可以使用 Floyd，并且这题的数据范围是 $2\leqslant n\leqslant70$，众所周知，只要 $n$ 在 $200$ 以内都可以用 Floyd，所以我们就可以放心地去用 Floyd，但是题目里这样有一句话：

最多坐 $k$ 个不同的公交线路。

所以我们必须用两个数组分别存储上次和当前的结果。并且我们发现计算出来的结果很大，这里就引用鲁迅的一句话，大家看着办吧：

十年 OI 一场空，不开 long long 见祖宗。

【核心代码】

优化

k=min(k,n);//k的值过大，就要取k和n的最小值来提高效率

Floyd

for(int p=2;p<=k;p++)//因为连边也算一次操作，所以Floyd只用循环k-1次
{
	for(int i=1;i<=n;i++)//复制上次结果
		for(int j=1;j<=n;j++)f[i][j]=dis[i][j];
	for(int l=1;l<=n;l++)//Floyd模板
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)f[i][j]=min(f[i][j],dis[i][l]+e[l][j]);
	for(int i=1;i<=n;i++)//更新答案
		for(int j=1;j<=n;j++)dis[i][j]=f[i][j];
}

输出部分的特殊处理

while(q--)
{
    int c=fread(),d=fread();
    if(c==d)puts("0");//起点就是终点
    else if(dis[c][d]==INF)puts("-1");//无法到达
    else printf("%d\n",dis[c][d]);
}

【完整代码】

高尔基曾经说过：

莫抄袭，棕了你的名，空悲切！