`

【floyd的灵活运用】LOJ 1174 Commandos

阅读更多

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;
}

 

1
0
分享到:
评论

相关推荐

    Floyd算法 Floyd算法

    中国数学建模-数学工具-Floyd最短路算法的MATLAB程序 wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 &gt;&gt; Matlab,Mathematica,maple,几何画板,word,sas,spss......

    floyd_路径规划_Floyd算法_dynamicdijkstra_

    "Floyd_路径规划_Floyd算法_dynamicdijkstra"这一主题主要涵盖了计算机科学中的路径规划问题,特别是Floyd算法的运用以及与Dijkstra算法的比较。本文将深入探讨Floyd算法的核心思想、实现过程、适用场景以及它与动态...

    Floyd最短路径java实现

    **Floyd最短路径算法详解** Floyd-Warshall算法是一种经典的解决图中所有顶点对最短路径问题的算法,由美国计算机科学家Robert W. Floyd于1962年提出。该算法的核心思想是逐步考虑更多的中间节点,通过动态规划的...

    Floyd算法_路径_floyd_matlab_

    **Floyd算法** Floyd算法,也称为Floyd-Warshall算法,是图论中用于查找有向图或无向图中所有顶点之间最短路径的一种经典算法。该算法由Robert Floyd在1962年提出,适用于解决多源最短路径问题,即寻找从图中的一个...

    floyd_matlab_

    在这个项目中,开发者利用MATLAB的灵活性和效率,编写了“floyd.m”这个脚本来实现Floyd算法。 Floyd算法的基本思想是通过迭代的方式逐步找出图中所有顶点对之间的最短路径。它通过一个二维数组(在这里可能是用...

    基于MATLAB的Floyd算法

    基于MATLAB的Floyd算法,计算网络中任意结点间的最小距离!

    floyd最短路径算法

    总结来说,Floyd算法是一种高效、灵活的求解多源最短路径问题的方法,通过动态规划逐步完善最短路径信息,具有广泛的实用价值。理解和掌握这一算法,对于从事图论、数据结构、网络优化等领域的工作有着重要意义。

    Floyd算法(可以输出最佳路径路线)

    Floyd算法,也被称为Floyd-Warshall算法,是图论中的一个重要算法,主要用于求解图中所有顶点之间的最短路径。这个算法由Robert Floyd和Stephen Warshall独立提出,因此得名。在计算机科学中,它常被用于解决网络...

    Floyd最短路径算法C++实现

    通过阅读和理解这个文件,你可以学习如何在实际编程中运用Floyd算法,了解如何构建邻接矩阵,以及如何组织代码来执行动态规划步骤。 总的来说,Floyd算法是一种强大的图算法,能够找到图中所有顶点对之间的最短路径...

    Floyd算法在配送中心选址的应用

    总结,Floyd算法凭借其高效性和灵活性,为配送中心选址提供了有力的工具。通过对所有可能的路径进行动态优化,企业能够在满足服务需求的同时,最大限度地降低运输成本,提升整体运营效率。在当今竞争激烈的物流市场...

    Floyd算法.rar

    **Floyd算法详解** Floyd算法,也被称为Floyd-Warshall算法,是图论中的一个经典算法,主要用于解决在加权图中寻找任意两个顶点之间的最短路径问题。这个算法是由美国计算机科学家Robert W. Floyd提出的,因此得名...

    最短路径算法 floyd

    Floyd-Warshall算法,通常简称为Floyd算法,是解决这一问题的有效方法之一。该算法由Robert Floyd和Stephen Warshall分别独立提出,因此得名。在本篇中,我们将深入探讨Floyd算法的基本原理、实现过程以及它在实际...

    Floyd-Steinberg抖动算法

    利用误差扩散算法中的Floyd-Steinberg抖动算法来对图像进行二值化处理,从而方便图像调频加网输出Floyd-Steinberg

    floyd算法求最短路径

    **Floyd算法详解** Floyd算法,又称为Floyd-Warshall算法,是解决图论中最短路径问题的一种经典算法。该算法的核心思想是通过动态规划的方法,逐步更新图中所有节点之间的最短路径,最终得到任意两个节点间的最短...

    Floyd最短路算法的MATLAB程序

    标题与描述中的核心知识点是关于Floyd最短路径算法在MATLAB环境下的实现与应用,尤其是在数学...对于从事数学建模、计算机科学、交通运输规划等领域的研究者和工程师而言,深入理解和灵活运用Floyd算法是十分必要的。

    使用c++,调用mpi进行floyd并向计算floyd2.cpp

    使用c++,调用mpi进行floyd并向计算

    floyd算法matlab通用程序

    本代码是floyd算法的通用matlab程序,代码写的十分经典,是数模比赛的利器

    校园导游图 C# floyd算法

    【标题】"校园导游图 C# floyd算法" 涉及到的主要技术点是C#编程语言的应用以及Floyd算法在路径查询中的应用。C#是一种广泛用于开发Windows应用程序、Web应用程序和移动应用程序的强大现代编程语言。在这个项目中,...

    Floyd算法c语言实现

    Floyd算法,又称为Floyd-Warshall算法,是解决图论中的最短路径问题的一种经典方法。在计算机科学中,特别是在算法设计领域,它被广泛应用于网络路由和行程规划。C语言作为基础的编程语言,是实现这种算法的理想选择...

    floyd算法m文件

    floyd算法m文件

Global site tag (gtag.js) - Google Analytics