原题链接
写了这题才真正知道(Floyed)本质。
最原始的(Floyed),(f[k][i][j])表示的是以(i)为起点,(j)为终点,路径上的点的编号不超过(k)的最短距离。
所以这题的修复时间恰好就是(Floyed)中(k)这一维的递增转移,边询问边接着跑(Floyed)即可。
时间复杂度:(O(n^3 + Q))
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 210;
int dis[N][N], T[N];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline int minn(int x, int y){ return x < y ? x : y; }
int main()
{
int i, j, k = 1, n, m, x, y, z, t;
n = re();
m = re();
for (i = 1; i <= n; i++)
T[i] = re();
memset(dis, 60, sizeof(dis));
for (i = 1; i <= m; i++)
{
x = re() + 1;
y = re() + 1;
z = re();
dis[x][y] = dis[y][x] = z;
}
t = re();
while (t--)
{
x = re() + 1;
y = re() + 1;
z = re();
for (; T[k] <= z && k <= n; k++)
for (i = 1; i <= n; i++)
if (i ^ k)
for (j = 1; j <= n; j++)
if (i ^ j && j ^ k)
dis[i][j] = dis[j][i] = minn(dis[i][j], dis[i][k] + dis[k][j]);
dis[x][y] < 1e9 && T[x] <= z && T[y] <= z ? printf("%d
", dis[x][y]) : printf("-1
");
}
return 0;
}