P8312题解

· · 题解

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

个人博客食用效果更佳

题目传送门

【分析】

其实这道题就是给你一个有 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]);
}

【完整代码】

高尔基曾经说过：

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