The Floyd algorithm is a critical component in solving this problem. Its essential to understand the underlying logic of the standard implementation.

for(int k=1; k<=n; ++k)
    for(int i=1; i<=n; ++i) {
        if(k == i) continue;
        for(int j=1; j<=n; ++j) {
            if(k == j || i == j) continue;
            if(dist[i][j] > dist[i][k] + dist[k][j])
                dist[i][j] = dist[i][k] + dist[k][j];
        }
    }

Each iteration of the k loop considers the shortest paths that use only the first k-1 nodes as intermediaries. The correctness stems from the fact that after processsing the first k-1 nodes, the current shortest path between any two nodes is guaranteed to be optimal. This allows the algorithm to consider new paths through node k and update the distances accordingly.

For this specific problem, the approach involves dynamically updating the distance matrix based on the reconstruction timeline. Each query checks whether the required nodes have been restored before accessing their shortest path.

#include <bits/stdc++.h>
#define pb push_back
using namespace std;

template <typename T> inline void read(T& t) {
    t = 0; register char ch = getchar(); register int fflag = 1;
    while (!('0' <= ch && ch <= '9')) { if (ch == '-') fflag = -1; ch = getchar(); }
    while (('0' <= ch && ch <= '9')) { t = ((t << 1) + (t << 3)) + ch - '0'; ch = getchar(); } t *= fflag;
}

template <typename T, typename... Args> inline void read(T& t, Args&... args) {
    read(t); read(args...);
}

template <typename T> inline void write(T x) {
    if (x < 0) putchar('-'), x = ~(x - 1); int s[40], top = 0;
    while (x) s[++top] = x % 10, x /= 10; if (!top) s[++top] = 0;
    while (top) putchar(s[top--] + '0');
}

const int MAXN = 205;
int dist[MAXN][MAXN], n, m, time_values[MAXN], queries, current_k;

void update_distances() {
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            if (dist[i][j] > dist[i][current_k] + dist[current_k][j])
                dist[i][j] = dist[j][i] = dist[i][current_k] + dist[current_k][j];
}

int main() {
    read(n, m);
    memset(dist, 0x3f, sizeof(dist));
    for (int i = 0; i < n; ++i) {
        read(time_values[i]);
        dist[i][i] = 0;
    }

    while (m--) {
        int u, v, w;
        read(u, v, w);
        dist[u][v] = dist[v][u] = w;
    }

    read(queries);
    while (queries--) {
        int u, v, time;
        read(u, v, time);
        while (time >= time_values[current_k] && current_k < n) {
            update_distances();
            ++current_k;
        }
        if (time < time_values[u] || time < time_values[v])
            cout << -1 << endl;
        else if (dist[u][v] == 0x3f3f3f3f)
            cout << -1 << endl;
        else
            cout << dist[u][v] << endl;
    }
    return 0;
}