Enfoque basado en Dijkstra: Este método presenta un rendimiento limitado, logrando solo 70 puntos en algunas pruebas, con una complejidad de O(n^3 log m). Es posible optimizarlo a Θ(n^3 log m + n), pero no se detallará aquí.

// Versión con Dijkstra
#include<stdio.h>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;

inline int leerEntero(){
    int valor=0,signo=1;
    char caracter=getchar();
    while(caracter<'0'||caracter>'9'){
        if(caracter=='-') signo=-1;
        caracter=getchar();
    }
    while(caracter>='0' && caracter<='9'){
        valor=valor*10+caracter-'0';
        caracter=getchar();
    }
    return valor*signo;
}

const int MAX_N=205, INFINITO=(1<<30)-1+(1<<30);
int tiempos[MAX_N], numNodos, numAristas, distancias[MAX_N][MAX_N][MAX_N];
bool reconstruido[MAX_N], visitado[MAX_N]={};

struct Arista{
    int destino, peso;
    Arista(int d, int p):destino(d),peso(p){}
};

vector<Arista> listaAdyacencia[MAX_N];

struct Nodo{
    int vertice, distancia;
    Nodo(int v, int d):vertice(v),distancia(d){}
    bool operator<(const Nodo &otro) const{return distancia>otro.distancia;}
};

void ejecutarDijkstra(int origen, int etapa){
    memset(visitado, 0, sizeof(visitado));
    for(int i=1;i<=numNodos;i++) distancias[etapa][origen][i]=distancias[etapa][i][origen]=INFINITO;
    if(!reconstruido[origen]) return;
    distancias[etapa][origen][origen]=0;
    priority_queue<Nodo> cola;
    cola.push(Nodo(origen,0));
    while(!cola.empty()){
        int actual=cola.top().vertice;
        cola.pop();
        if(!visitado[actual]){
            visitado[actual]=1;
            for(int i=0;i<listaAdyacencia[actual].size();i++){
                int vecino=listaAdyacencia[actual][i].destino;
                int costo=listaAdyacencia[actual][i].peso;
                if(!visitado[vecino] && reconstruido[vecino] && distancias[etapa][origen][vecino]>distancias[etapa][origen][actual]+costo){
                    distancias[etapa][origen][vecino]=distancias[etapa][vecino][origen]=distancias[etapa][origen][actual]+costo;
                    cola.push(Nodo(vecino,distancias[etapa][origen][vecino]));
                }
            }
        }
    }
}

int buscarIndice(int limite){
    int contador=0;
    for(int i=1;i<=numNodos;i++){
        if(tiempos[i]>limite) break;
        if(tiempos[i]==tiempos[i+1] && i<numNodos) contador--;
    }
    return contador + i - 1;
}

int main(){
    int a,b,peso;
    numNodos=leerEntero(), numAristas=leerEntero();
    for(int i=1;i<=numNodos;i++) tiempos[i]=leerEntero();
    for(int i=1;i<=numAristas;i++){
        a=leerEntero(), b=leerEntero(), peso=leerEntero();
        a++, b++;
        listaAdyacencia[a].push_back(Arista(b,peso));
        listaAdyacencia[b].push_back(Arista(a,peso));
    }
    for(int i=1, etapa=0;i<=numNodos;i++){
        etapa++;
        reconstruido[i]=1;
        while(i<numNodos && tiempos[i]==tiempos[i+1]) reconstruido[++i]=1;
        for(int j=1;j<=numNodos;j++) ejecutarDijkstra(j,etapa);
    }
    int consultas;
    consultas=leerEntero();
    while(consultas--){
        a=leerEntero(), b=leerEntero(), int tiempoConsulta=leerEntero();
        a++, b++;
        int indice=buscarIndice(tiempoConsulta);
        if(indice==0 || distancias[indice][a][b]>=INFINITO-3) puts("-1");
        else printf("%d\n",distancias[indice][a][b]);
    }
    return 0;
}

Enfoque basado en Floyd-Warshall: Este es el método óptimo con una complejidad de O(n^3). La clave está en que los tiempos de reconstrucción forman una secuencia no decreciente, lo que permite procesar las consultas en orden.

// Versión con Floyd-Warshall
#include<bits/stdc++.h>
using namespace std;

const int INFINITO=1e8, MAX_N=210;
int matrizDist[MAX_N][MAX_N], limiteActual;
int numNodos, numAristas, numConsultas, tiempos[MAX_N];

int main(){
    scanf("%d%d",&numNodos,&numAristas);
    for(int i=0;i<numNodos;i++)
        for(int j=0;j<numNodos;j++)
            matrizDist[i][j]=INFINITO;
    for(int i=0;i<numNodos;i++){
        scanf("%d",&tiempos[i]);
        matrizDist[i][i]=0;
    }
    for(int i=0;i<numAristas;i++){
        int u,v,peso;
        scanf("%d%d%d",&u,&v,&peso);
        matrizDist[u][v]=matrizDist[v][u]=peso;
    }
    scanf("%d",&numConsultas);
    while(numConsultas--){
        int origen,destino,tiempoPeticion;
        scanf("%d%d%d",&origen,&destino,&tiempoPeticion);
        for(int k=limiteActual;k<numNodos && tiempos[k]<=tiempoPeticion;k++,limiteActual++)
            for(int i=0;i<numNodos;i++)
                for(int j=0;j<numNodos;j++)
                    matrizDist[i][j]=min(matrizDist[i][j],matrizDist[i][k]+matrizDist[k][j]);
        if(tiempos[origen]<=tiempoPeticion && tiempos[destino]<=tiempoPeticion && matrizDist[origen][destino]<INFINITO)
            printf("%d\n",matrizDist[origen][destino]);
        else puts("-1");
    }
    return 0;
}