自助外贸英文网站建设/百度关键词优化手段

Floyd算法是多源汇最短路算法，可以处理自环和重边
d[a][b] 记录了图中从节点a到节点b的距离
Floyd基于动态规划
Floyd代码真的很简单

核心代码

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

完整代码

#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;const int N = 210, INF = 1e9;int n, m, Q;
// 邻接矩阵
int d[N][N]; // 简单的离谱了void floyd()
{for (int k = 1; k <= n; ++k)for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}int main()
{scanf("%d%d%d", &n, &m, &Q);for (int i = 1; i <= n; ++i)for (int j = 1; j <= n; ++j)if (i == j) d[i][j] == 0;else d[i][j] = INF;while(m--){int a, b, w;cin >> a >> b >> w;d[a][b] = min(d[a][b], w);}floyd();while(Q--){int a, b;scanf("%d%d", &a, &b);if (d[a][b] > INF / 2) puts("impossible");else printf("%d\n", d[a][b]);}return 0;
}