网站 › 『编程语言讨论求助区』 › 多元汇最短路算法：Floyd 学习笔记

RainPPR 发表于 2022-12-24 19:11

多元汇最短路算法：Floyd 学习笔记

# Floyd

求多元汇最短路
基于动态规划
复杂度：`O(n^3)`

## 思路
1. 用邻接矩阵存储
`d` 存储所有的边
2. 三重循环：
`for k : 1 ~ n`
`for i : 1 ~ n`
`for j : 1 ~ n`
`d = min(d, d + d);`

## 原理
`d = d + d`
动态规划降维就OK

## 代码
代码比较简单，没写注释
```cpp
#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

const int N = 210, INF = 1e9;

int n, m, Q;
int d;      // 邻接矩阵

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

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 = 0;
      else
                d = INF;
      
      int a, b, w;
      while (m--)
      {
                scanf("%d %d %d", &a, &b, &w);
                d = min(d, w);
      }
      
      floyd();
      
      while (Q--)
      {
                scanf("%d %d", &a, &b);
                int t = d;
                if (t > INF / 2)
                        printf("impossible\n");
                else
                        printf("%d\n", d);
      }
      return 0;
}
```

King1993 发表于 2022-12-25 00:30

谢谢分享，学习了

查看完整版本: 多元汇最短路算法：Floyd 学习笔记