知识概览
例题展示
题目链接
活动 - AcWing 系统讲解常用算法与数据结构,给出相应代码模板,并会布置、讲解相应的基础算法题目。https://www.acwing.com/problem/content/856/
题解
Floyd算法基于动态规划的思想,主要是三重循环,先遍历k,i和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;
scanf("%d%d%d", &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;
}
参考资料
- AcWing算法基础课