本题基本上是Floyd的模版题,适合初学Floyd的OIer练习。

本题的重点在于并非在每一个时刻,每一个节点都可以到达,所以应枚举目前所有可以到达的节点k,并以k为中转点进行更新。

同时,因为出题人已经给数据排好了顺序,发现未建成时直接中断即可。

闲话少说,主要看代码注释。

#include<cstdio> 
#include<algorithm>
using namespace std;

const int MAXN = 200 + 5;
const int INF = 1e9;

int edge[MAXN][MAXN], times[MAXN];
int n, m, q;

/*
init()函数:
Floyd初始化
*/
void init() {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            edge[i][j] = (i == j ? 0 : INF);//节点到自身的距离为0
        }
    }
}

/*
addEdge()函数:
在邻接矩阵中添加一条(双向)边
*/
void addEdge(int i, int j, int v) {
    edge[i][j] = edge[j][i] = v;//双向边处理
}

/*
input()函数:
输入数据
*/
void input() {
    scanf("%d%d", &n, &m);
    init(); //读入n, m后进行初始化
    for(int i = 0; i < n; i++) {
        scanf("%d", &times[i]);
    }
    for(int i = 0; i < m; i++) {
        int x, y, v;

        scanf("%d%d%d", &x, &y, &v);
        addEdge(x, y, v);
    }
}

/*
update()函数:
以k为中转点更新最短路
*/
void update(int k) {
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            edge[i][j] = min(edge[i][j], edge[i][k] + edge[k][j]);
        }
    }
}

void work() {
    int cur = 0;

    scanf("%d", &q);
    for(int i = 0; i < q; i++) {
        int x, y, t;

        scanf("%d%d%d", &x, &y, &t);

        //这里是重点
        while(times[cur] <= t && cur < n) {
            update(cur);//若当前可以经过村庄cur,以cur为中转点更新最短路径
                        cur++;
        }
        if(times[x] > t || times[y] > t || edge[x][y] == INF) {
            printf("-1\n");//村庄x尚未建成,村庄x尚未建成或村庄x与村庄y在t时并不连通
        } else {
            printf("%d\n", edge[x][y]);
        }
    }
}

int main() { //简洁的main()函数
    input();
    work();

    return 0;
}