经典Floyd求最短路算法（速成版）

#include <iostream>
#include <vector>

using namespace std;
const int INF = 0x3f3f3f3f;

int n, m, k, u, v, w;

// Floyd 多源最短路的算法流程
// Time Complexity: O(N^3)
int main(void) {
  scanf("%d %d %d", &n, &m, &k);

  // 初始化邻接矩阵，一开始存的是图！
  vector<vector<int>> matrix(n + 1, vector<int>(n + 1)); // adjacence matrix
  for (int u = 1; u <= n; ++u)
    for (int v = 1; v <= n; ++v)
      if (u == v) matrix[u][v] = 0; // 对角线上的元素 （自已到自已的距离为0）
      else matrix[u][v] = INF;

  while (m--) {
    scanf("%d %d %d", &u, &v, &w);
    matrix[u][v] = min(matrix[u][v], w); // 图中可能存在重边 (平行边)，因此取一条最短边
  }

  // Floyd 又称3F算法 （因为它有3个For循环)
  // 细节慢慢证明 （先背过!!!）
  for (int k = 1; k <= n; ++k)
    for (int u = 1; u <= n; ++u)
      for (int v = 1; v <= n; ++v)
        if (matrix[u][k] + matrix[k][v] < matrix[u][v])
          matrix[u][v] = matrix[u][k] + matrix[k][v];


  while (k--) {
    cin >> u >> v;
    if (matrix[u][v] > INF / 2) puts("impossible");
    else printf("%d\n", matrix[u][v]);
  }

  return 0;
}