你好！我是你的OI金牌教练。

在上一道关于“玄奘西行”的题目中，我们学习了单源最短路径（Dijkstra）算法。它解决的是“从某一个起点出发，到达其他所有点的最短距离”。

今天，我们将时间轴拨回春秋战国时期，跟随至圣先师孔子的脚步，结合 “孔子周游列国” 的历史背景，学习图论中另一个经典的算法——Floyd-Warshall 算法（简称 Floyd 算法）。

这道题在知识点上与 Dijkstra 有明显的递进关系：

1. Dijkstra 解决的是 “一对多”（单源）的最短路，基于贪心思想。
2. Floyd 解决的是 “多对多”（全源）的最短路，基于动态规划 (DP) 思想。

第一部分：背景知识讲解

1. 孔子周游列国 (Confucius' Travels)

春秋末期，礼崩乐坏。为了推行自己的政治主张（“仁”与“礼”），孔子带领弟子离开鲁国，开始了长达14年的周游列国之旅。他先后到了卫、陈、蔡、楚等国，虽未被重用，却传播了儒家思想，并在此过程中修订了《六经》。

2. 诸侯国的交通网络

春秋时期，诸侯国林立，国与国之间有官道相连。 如果孔子想从鲁国去往楚国，他可能需要经过卫国、宋国等中转。 作为一个旅行团的“向导”，如果不仅要知道“鲁国出发去各地”的距离，还需要随时回答“从卫国到陈国有多远”、“从宋国到蔡国有多远”等任意两个国家之间的距离，如果每次都重新跑一遍 Dijkstra 算法，代码写起来比较繁琐。

3. 算法模型：多源最短路径 (All-Pairs Shortest Path)

我们需要求出图中任意两点 $(u, v)$ 之间的最短路径。

• 状态定义：$dp[k][i][j]$ 表示“只允许以节点 $1 \sim k$ 作为中转站的情况下，从 $i$ 到 $j$ 的最短距离”。
• 状态转移：
  • 如果不经过节点 $k$ 中转：距离就是 $dp[k-1][i][j]$。
  • 如果经过节点 $k$ 中转：距离就是 $dp[k-1][i][k] + dp[k-1][k][j]$。
  • 取最小值：$dp[k][i][j] = \min(dp[k-1][i][j], \quad dp[k-1][i][k] + dp[k-1][k][j])$。
• 空间优化：第一维 $k$ 可以省略。核心代码只有三层循环：

  for (k = 1; k <= N; k++)
      for (i = 1; i <= N; i++)
          for (j = 1; j <= N; j++)
              dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
  

第二部分：题目内容

题目名称：周游列国 (Touring the States)

题目描述

春秋时期，中原大地分布着 $N$ 个诸侯国，编号为 $1$ 到 $N$。 各国之间修建了 $M$ 条双向官道。第 $i$ 条官道连接了国家 $u_i$ 和 $v_i$，通行需要耗费 $w_i$ 的时间。

孔子带着弟子们在各国间游历讲学。为了规划行程，颜回（孔子的弟子）需要频繁地向你查询路线信息。 共有 $Q$ 次询问，每次询问给定起点 $S$ 和终点 $T$，请你回答从国家 $S$ 到国家 $T$ 的最短通行时间。

注意：虽然地图是连通的，但某些偏远国家之间可能无法到达（虽然题目背景通常是连通的，但算法要考虑不连通情况）。如果无法到达，输出 -1。

输入格式

第一行包含三个正整数 $N, M, Q$。

• $N$ 表示诸侯国的数量。
• $M$ 表示官道的数量。
• $Q$ 表示询问的数量。

接下来 $M$ 行，每行包含三个正整数 $u, v, w$。

• 表示国家 $u$ 和 $v$ 之间有一条耗时为 $w$ 的双向道路。
• 注意：两个国家之间可能有多条道路，应取最短的一条；可能存在自环（忽略即可）。

接下来 $Q$ 行，每行包含两个正整数 $S, T$，表示一次查询。

输出格式

输出 $Q$ 行，每行一个整数，表示最短通行时间。如果不可达，输出 -1。

输入输出样例 #1

输入：

4 4 3
1 2 2
2 3 3
1 3 6
3 4 2
1 3
1 4
2 4

输出：

5
7
5

样例 #1 解释：

• 1 到 3：
  • 直接走：$1 \to 3$，耗时 6。
  • 经 2 中转：$1 \to 2 \to 3$，耗时 $2+3=5$。
  • 最短为 5。
• 1 到 4：
  • 经 3 中转：$1 \to (\dots) \to 3 \to 4$。
  • 因为 $1 \to 3$ 最短是 5，所以 $1 \to 4$ 最短是 $5+2=7$。
• 2 到 4：
  • $2 \to 3 \to 4$，耗时 $3+2=5$。

输入输出样例 #2

输入：

3 1 2
1 2 10
1 3
2 3

输出：

-1
-1

样例 #2 解释： 只有 1 和 2 之间有路。3 是孤立的，无法到达。

数据范围

对于 $100\%$ 的数据：

• $1 \le N \le 200$ （注意：Floyd算法是 $O(N^3)$，所以 N 通常很小）
• $1 \le M \le 10000$
• $1 \le Q \le 10000$
• $1 \le w \le 1000$