题目背景
B 地震后，所有村庄都造成了一定的损坏，但地震对公路没有影响。但在村庄重建之前，所有未重建的村庄的道路都不能通车。换句话说，只有连接两个重建村庄的道路才能通车，只能到达重建村庄。
题目描述
给出 B 该地区的村庄数量NN，村庄编号从0到N?1，和所有M公路长度为双向。并给出第i村庄重建完成的时间ti，你可以认为它是同时重建的ti天重建完成，当天即可通车。若ti为0说明地震没有损坏这个地区，一开始就可以通车。之后有Q个询问(x,y,t)(x,y,t)，你必须回答每一个问题。t天，从村庄x到村庄y最短路径长度是多少？若找不到从x村庄到y村庄的路径经过几个重建的村庄或村庄x或村庄y在第t天还没有重建，需要返回-1。
输入格式
第一行包括两个正整数N,MN,M，表示村庄和公路的数量。
第二行包含NN个非负整数t_0, t_1,…, t_{N-1}t0,t1,…,tN?1.表示每个村庄重建的时间，数据得到保证t_0 ≤ t_1 ≤ … ≤ t_{N-1}t0≤t1≤…≤tN?1。
接下来MM每行33个非负整数i, j, wi,j,w，ww对于不超过100010000的正整数，表示有一个连接村庄ii与村庄jj长度为ww，保证i≠ji=j，任何一对村庄只有一条路。
下一行就是M 3M 三行包含正整数QQ，表示QQ个询问。
接下来QQ每行33个非负整数x, y, tx,y,t，询问在第tt天，从村庄xx到村庄yy数据保证了最短路径的长度tt不下降。
输出格式
共QQ好吧，每一个问题(x, y, t)(x,y,t)输出相应的答案，即在第一位tt天，从村庄xx到村庄yy最短路径的长度是多少？如果在第二天找不到从xx村庄到yy村庄的路径经过几个已经重建的村庄，或者x或村庄yy在第tt天还没修好，输出-1?1。
输入输出样例
复制
4 5 1 2 3 4 0 2 1 2 3 1 3 1 2 2 1 4 0 3 5 4 2 0 2 0 1 2 0 1 3 0 1 4复制
-1 -1 5 4说明/提示
对于30\0%的数据，N≤50N≤50；
对于30\0%的数据，t_i= 0ti=0，其中有20\ %的数据有t_i = 0ti=0且N>50N>50；
对于50\P%数据，有Q≤100Q≤100；
对于100\0%的数据，有N≤200N≤200，M≤N \times (N-1)/2M≤N×(N?1)/2，Q≤50000Q≤所有输入数据涉及的总数不超过1万万。
多源汇最短路问题
如果只会floyd模板这个问题做不到，
for(int k=1;k<=n;k ) for(int i=1;i<=n;i ) for(int j=1;j<=n;j ) dist[i][j]=min(dist[i][j],dist[i][k] dist[k][j]);用前k点更新更新过程i，j两点之间的距离，这个问题是否可以通过村庄的时间限制和随时增加
故将floyd()变成这样:
void floyd(int k) { for(int i=1;i<=n;i ) for(int j=1;j<=n;j ) dist[i][j]=min(dist[i][k] dist[k][j],dist[i][j]); }因为询问给出的t增加，所以输入时更新；
#include <iostream> #include <cstring> using namespace std; int g[210][210],a[210]; const int inf=0x3f3f3f3f; int n,m,t; void floyd(int k) { for(int i=1;i<=n;i ) for(int j=1;j<=n;j ) g[i][j]=min(g[i][j],g[i][k] g[k][j]); } int main() { int u,v,w; cin>>n>>m; for(int i=1;i<=n;i ){ for(int j=1;j<=n;j ) if(i==j) g[i][j]=0; else g[i][j]=inf; } for(int i=1;i<=n;i ) scanf("%d",&a[i]); while(m--){ scanf("%d%d%d",&u,&v,&w); u ,v ; g[u][v]=g[v][u]=w; } cin>>t; int cur=1; while(t--) { scanf("%d%d%d",&u,&v,&w); u ,v ; while(a[cur]<=w&&cur<=n) {floyd(cur);cur ;} //边输入边更新 if(a[u]>w||a[v]>w||g[u][v]==inf) printf("-1\n"); else printf("%d\n",g[u][v]); } return 0; }