KIDx的解题报告
题目链接:http://lightoj.com/volume_showproblem.php?problem=1174
题意:无限支军队从起点出发,最少要多长时间路过所有城市并且到达终点?
利用folyd 插点法的思想即可解决
找到dist[s][i] + dist[i][t]的最大值即为所求最小值
#include <iostream>
using namespace std;
#define M 105
#define inf 0x3fffffff
int dist[M][M], n;
void init ()
{
int i, j;
for (i = 0; i < n; i++)
{
dist[i][i] = 0;
for (j = i + 1; j < n; j++)
dist[i][j] = dist[j][i] = inf;
}
}
void floyd ()
{
int i, j, k;
for (k = 0; k < n; k++)
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
if (dist[i][k] != inf && dist[k][j] != inf &&
dist[i][k] + dist[k][j] < dist[i][j])
dist[i][j] = dist[i][k] + dist[k][j];
}
int main()
{
int t, cc = 1, q, a, b, s, e, ans, i;
scanf ("%d", &t);
while (t--)
{
scanf ("%d%d", &n, &q);
init();
while (q--)
{
scanf ("%d%d", &a, &b);
dist[a][b] = dist[b][a] = 1;
}
floyd ();
scanf ("%d%d", &s, &e);
ans = 0;
for (i = 0; i < n; i++)
{
if (dist[s][i] == inf || dist[i][e] == inf)
continue;
int tp = dist[s][i] + dist[i][e];
if (tp > ans)
ans = tp;
}
printf ("Case %d: %d\n", cc++, ans);
}
return 0;
}
分享到:
相关推荐
中国数学建模-数学工具-Floyd最短路算法的MATLAB程序 wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 >> Matlab,Mathematica,maple,几何画板,word,sas,spss......
基于MATLAB的Floyd算法,计算网络中任意结点间的最小距离!
Floyd最短路径算法的java实现,文件内附测试用例拓扑。
C# floyd算法 求最短路径 C# floyd算法 求最短路径 C# floyd算法 求最短路径
Floyd算法 详细介绍了Floyd算法的应用
利用误差扩散算法中的Floyd-Steinberg抖动算法来对图像进行二值化处理,从而方便图像调频加网输出Floyd-Steinberg
最短路径算法 floyd
使用c++,调用mpi进行floyd并向计算
本代码是floyd算法的通用matlab程序,代码写的十分经典,是数模比赛的利器
floyd算法m文件
使用Floyd算法,求解点对之间的最短距离。图结构使用邻接矩阵存储。
matlab实现的floyd算法,matlab实现的floyd算法
floyd算法,C语言编写的程序,适合学生作业。非常专业
Floyd算法.doc
更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd弗洛伊德算法更新6 floyd...
floyd最短路算法 最短路程序
floyd 源代码 matlab floyd算法的matlab源代码实现
Floyd算法是经典的最短路径算法之一,应用广泛,可以求解多对多和一对一的最短路;
求最短路径的Floyd算法实现,无向图和有向图均适用。1先区别有向图和无向图,2输入顶点数和边数并检查合法性,3输入每边的起点、终点、权重并检查合法性,并初始化邻接矩阵和路径矩阵,4调用自定义函数Floyd
Floyd是数据结构中解决求解图中多源点最短路径问题的经典算法,文件中包括算法实现和详细分析,下载可直接运行调试,可供数据结构与算法课程的学习