本文主要是介绍Floyed算法练习题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
**例题:**顶点个数n<=100, m条边, 两点之间的距离w<=1000,求给定两点p、 q之间的最短距离。 输入数据, 第一行4个整数n m p q, 接下来有m行, 每行三个数依次描述了一条边的起点、 终点和权值。
程序里面有彩蛋o!
#include <iostream>
#include <cstring>
#include <cstdio> // 孙艺轩是周雨涵的同学兼好朋友(我该死)
// 周雨涵经常对任老师说:妈妈,老师有批评我了
// 所以周雨涵情商低 (老师说的)
using namespace std;int d[1010][10100];int main()
{int n, m, p, q;cin >> n >> m >> p >> q;memset(d, 0x3f, sizeof d);for(int i = 1; i <= n; i ++){d[i][i] = 0;}for(int i = 1; i <= m; i ++){int a, b, c;scanf("%d%d%d", &a, &b, &c);if(d[a][b] > c){d[a][b] = d[b][a] = c;}}for(int k = 1; k <= n; k ++){for(int i = 1; i <= n; i ++){for(int j = 1; j <= n;j++){if(d[i][k]+d[k][j]<d[i][j]){d[i][j]=d[i][k]+d[k][j];}}}}printf("%d\n",d[p][q]);return 0;
}
这篇关于Floyed算法练习题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!