Noob Dream

 找回密码
 加入我们[Register]
搜索
查看: 103|回复: 0

最短路算法(Floyd)

[复制链接]

21

主题

21

帖子

112

积分

超级版主

Rank: 8Rank: 8

积分
112
发表于 2018-5-6 14:01:48 | 显示全部楼层 |阅读模式
floyd可以计算任意点对之间的距离
复杂度O(n^3)
代码:
[C++] 纯文本查看 复制代码
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f
const int maxn = 105;
int mpt[maxn][maxn];
int n, m;

void floyd() {
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                mpt[i][j] = min(mpt[i][k] + mpt[k][j], mpt[i][j]);
            }
        }
    }
}

int main() {
    while (scanf("%d%d", &n, &m) != EOF) {
        if (n + m == 0) break;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j) mpt[i][j] = 0;
                else mpt[i][j] = INF;
            }
        }
        for (int i = 1; i <= m; i++) {
            int a, b, c;
            scanf("%d%d%d", &a, &b, &c);
            if (c < mpt[a][b]) {
                mpt[a][b] = c;
                mpt[b][a] = c;
            }
        }
        floyd();
        printf("%d\n",mpt[1][n]);
    }
    return 0;
}

回复

使用道具 举报

本版积分规则

QQ|Noob Dream

GMT+8, 2018-8-15 12:54 , Processed in 0.119278 second(s), 23 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表