本文主要是介绍巧妙的运用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那答案就不对了。。。。顿时明白了，，。。我怎么没想到ＱＡＱ。。。还有ＴＬＥ不一定是超时啊，可能还有各种奇葩的错误导致的。。。。
正确解法：
如何判断最小路径中是否能够有ｃ点，只要判断ｄ［ａ］［ｂ］ ＝＝ ｄ［ａ］［ｃ］ ＋ ｄ［ｃ］［ｂ］相等则存在，不等则不存在。。。
#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 xxzfreopen("in.txt","r",stdin);#endif // xxzwhile(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算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
