首页 > 代码库 > 巧妙的运用Floyd算法

巧妙的运用Floyd算法

题目大概意思:输入n,m,n代表n个点,接着输入n个点之间的距离(n*n的矩阵),接下来m次询问,输入a,b,c如果a,b之间的最短路径中存在c点则输出Yes,否则输出No

比赛的时候没有做出来,赛后帆哥一点播就知道了。。。。我写的时候直接用floy算法求距离并记录路径。。然后TLE到死。。。我就奇怪了数据n,m都小于100,怎么会TLE啊。。。坑爹啊。。。我一直怀疑是不是用别的算法。。。。。帆哥说我记录的路径只是正确路径中的一条路径,比如1-3直接最短路径是2,但是可能1-2-3加起来也是2,但是你记录的路径是1-3而不是1-2-3那答案就不对了。。。。顿时明白了,,。。我怎么没想到QAQ。。。还有TLE不一定是超时啊,可能还有各种奇葩的错误导致的。。。。

正确解法:

如何判断最小路径中是否能够有c点,只要判断d[a][b] == d[a][c] + d[c][b]相等则存在,不等则不存在。。。

#include <iostream>
#include<cstdio>
#include <cstring>
using namespace std;
int d[150][150];
int w[150][150];
const int INF = 127;
int main()
{
    int n,m;
     #ifdef xxz
    freopen("in.txt","r",stdin);
    #endif // xxz
    while(cin>>n>>m)
    {
        memset(d,INF,sizeof(d));
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                cin>>d[i][j];


        for(int k = 1; k <= n; k++)
            for(int i = 1; i <= n; i++)
                for(int j = 1; j <= n; j++)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
                    
        while(m--)
        {
            int start,end,mid;
            cin>>start>>end>>mid;
            if(d[start][mid] + d[mid][end] == d[start][end]) cout<<"Yes"<<endl;
            else cout<<"No"<<endl;
        }

    }
    return 0;
}


巧妙的运用Floyd算法