经典问题----最短路径（Floyd弗洛伊德算法）（HDU2066）

问题简介：

给定T条路，S个起点，D个终点，求最短的起点到终点的距离。

思路简介：

弗洛伊德算法即先以a作为中转点，再以a、b作为中转点，直到所有的点都做过中转点，求得所有点到其他点的最短路径，Floyd算法适用于多源最短路径，是一种动态规划算法，稠密图效果最佳，边权可正可负。优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。缺点：时间复杂度比较高，不适合计算大量数据。Floyd算法时间复杂度为n^3,Dijikstra算法为n^2。

优化代码：

#include <iostream>

#include <cmath>

#include <stdio.h>

#include <cstdio>

#include <cstring>

#include<algorithm>

#include<time.h>

#include<math.h>

#include <stdlib.h>

#include <string.h>

#include <stack>  

using namespace std;

#define MAXN 1000000

#define N 1010

int map[N][N], s[N], e[N], maxx;

int T, S, D;

int floyd()

{

    int res = MAXN;

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

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

            if (map[i][k] != MAXN)//优化

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

                {

                    if (map[i][j]>map[i][k] + map[k][j])

                        map[i][j] = map[i][k] + map[k][j];

                    if (s[i] && e[j] && res>map[i][j])//因为是取最短的一条路径，所以随时记录起点到终点的路

                        res = map[i][j];

                }

    return res;

}

int main()

{

    while (scanf("%d%d%d", &T, &S, &D) != EOF)

    {

        memset(map, , sizeof(map));

        memset(s, , sizeof(s));

        memset(e, , sizeof(e));

        for (int i = ; i <= ; i++)//初始化

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

                map[i][j] = MAXN;

        int u, v, w;

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

        {

            scanf("%d%d%d", &u, &v, &w);

            maxx = max(maxx, max(u, v));

            map[u][v] = w;

        }

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

        {

            scanf("%d", &u);

            s[u] = ;//起点

        }

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

        {

            scanf("%d", &u);

            e[u] = ;//终点

        }

        printf("%d\n", floyd());

    }

    return ;

}

HDU2066

巴特西

经典问题----最短路径（Floyd弗洛伊德算法）（HDU2066）

最新文章

热门文章