本文共 2418 字，大约阅读时间需要 8 分钟。
我们面临一个典型的时间动态最短路径问题。给定一个无向图，点i的出现时间为t[i]。在q次查询中，我们需要回答在时间t时，从点x到点y的最短路径长度。需要注意的是，点的编号是按照出现时间顺序进行的，而查询也是按照时间顺序进行的。
本文采用Floyd算法（也称为费曼算法）来解决上述问题。Floyd算法的本质是一种动态规划算法，通过逐步更新点之间的最短距离，最终得到所有点对之间的最短路径。由于点和查询都是按照时间顺序给出的，我们可以利用这一特性，仅考虑查询时间之前的点作为中转点k。
选择Floyd算法的主要原因有以下几点：
我们采用以下步骤来实现上述思路：
初始化距离矩阵：创建一个n×n的距离矩阵f，其中f[i][j]表示点i到点j的最短距离。初始时，所有的距离设为无穷大，除了自身到自身的距离设为0。
更新距离矩阵：对于每个查询时间time，我们从1到time-1的点作为中转点k，更新所有点对之间的最短距离。具体来说，对于每对点(u, v)，我们检查是否通过点k可以得到更短的路径：f[u][v] = min(f[u][v], f[u][k] + f[k][v])。
处理查询：对于每个查询(time, u, v)，首先检查u和v在该时间点之前已经存在。如果t[u] > time || t[v] > time，说明该点尚未出现，直接返回-1。否则，查询结果即为当前距离矩阵中的f[u][v]。
#include#include #include inline int getint() { register char ch; while (!isdigit(ch = getchar())) ; // 等待数字字符 register int x = ch - '0'; while (isdigit(ch = getchar())) x = (x << 1) | (ch - '0'); return x;}const int INF = 0x7FFFFFFF;const int N = 200;int t[N], f[N][N];int main() { const int n = getint(), m = getint(); for (register int i = 0; i < n; ++i) t[i] = getint(); for (register int i = 0; i < n; ++i) { for (register int j = 0; j < n; ++j) { if (i == j) f[i][j] = 0; else f[i][j] = INF; } } for (register int q = 0; q < m; ++q) { int u = getint(), v = getint(), time = getint(); if (t[u] > time || t[v] > time) { puts("-1"); continue; } for (register int k = 0; k < n; ++k) { if (t[k] > time) break; for (register int i = 0; i < n; ++i++) { if (t[i] > time) break; for (register int j = 0; j < n; ++j++) { if (t[j] > time) break; if (f[i][j] > f[i][k] + f[k][j]) { f[i][j] = f[i][k] + f[k][j]; } } } } puts(f[u][v]); }}
这种方法充分利用了动态图的特性，确保在每次查询时都能得到正确的最短路径结果。
转载地址：http://rhhfk.baihongyu.com/