畅通工程续 -- HDU 1874 floyd

题目大意：

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

思路：

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

AC代码：

#include <iostream>
#include <cstdio>
#include <string.h>

using namespace std;
const int MX = 1000+10;
const int INF = 0x3f3f3f3f;
int n, m;
int mp[MX][MX];

void floyd()
{
    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; 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 = 0; i < n; ++i) mp[i][i] = 0;
        for(int i = 0; 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
", mp[from][to]);
        else printf("-1
");
    }
}

View Code

畅通工程续 -- HDU 1874 floyd

相关推荐