畅通工程续 -- HDU 1874 floyd

时间：2021-09-20 19:17:34

题目大意：

现在，已知起点和终点，请你计算出要从起点到终点，最短需要行走多少距离。

思路：

floyd算法模板题，这是一个牺牲空间换取时间的算法，本质是动态规划。

AC代码：

#include <iostream>

#include <cstdio>

#include <string.h>

using namespace std;

const int MX = +;

const int INF = 0x3f3f3f3f;

int n, m;

int mp[MX][MX];

void floyd()

{

    for(int k = ; k < n; ++k)

        for(int i = ; i < n; ++i)

            for(int j = ; j < n; ++j)

                mp[i][j] = min(mp[i][j], mp[i][k]+mp[k][j]);

}

int main()

{

    while(scanf("%d%d", &n, &m) != EOF)

    {

        memset(mp, INF, sizeof(mp));

        for(int i = ; i < n; ++i) mp[i][i] = ;

        for(int i = ; i < m; ++i)

        {

            int from, to, cost;

            scanf("%d%d%d", &from, &to, &cost);

            if(mp[from][to] > cost) mp[from][to] = mp[to][from] = cost; //这里注意A到B可能有多条路能到！

        }

        floyd();

        int from, to;

        scanf("%d%d", &from, &to);

        if(mp[from][to] != INF) printf("%d\n", mp[from][to]);

        else printf("-1\n");

    }

}

如有疑问，欢迎评论指出！

相关文章