P1119 灾后重建

//https://www.luogu.com.cn/problem/P1119?contestId=96617
//所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车
//只有两个村庄都建好了才可以赋边权
#include<bits/stdc++.h>
#define inf 1e9
using namespace std;
int n,m;
int t[200];
int G[200][200];
int Q;
int tt;
int midG[200][200];
struct Node
{
   int u;
   int v;
   int ttt;
};
Node Ques[50000];

bool visited[200];
int  dist[200];
int dijsktra(int start,int end)
{
   fill(visited,visited+200,false);
   fill(dist,dist+200,inf);
   dist[start]=0;
   for(int i=0;i<n;i++)
   {
       int u=-1;
       int min=inf;
       for(int j=0;j<n;j++)
       {
           if(visited[j]==false&&dist[j]<min)
           {
               u=j;
               min=dist[j];
           }
       }
       if(u==-1) return -1;
       visited[u]=true;
       for(int j=0;j<n;j++)
       {
           if(visited[j]==false&&midG[u][j]!=inf&&dist[j]>dist[u]+midG[u][j])
           {
               dist[j]=dist[u]+midG[u][j];
           }
       }
   }
   return dist[end];
}

int main()
{
   cin>>n>>m;
   for(int i=0;i<n;i++)
       cin>>t[i];
   fill(G[0],G[0]+200*200,inf);
   for(int i=0;i<n;i++)
       G[i][i]=0;
   for(int i=0;i<m;i++)
   {
       int u,v,w;
       cin>>u>>v>>w;
       G[u][v]=G[v][u]=w;
   }
   cin>>Q;
   for(int i=0;i<Q;i++)
   {
       int u,v,ttt;
       cin>>u>>v>>ttt;
       Ques[i].u=u;
       Ques[i].v=v;
       Ques[i].ttt=ttt;
   }
   fill(midG[0],midG[0]+200*200,inf);
   for(int i=0;i<n;i++)
       midG[i][i]=0;
   for(tt=0;tt<=t[n-1];tt++)
   {
       //随时间推移midG中的边逐渐增加
       //如果某个tt时刻i号村子修好了那么释放所有到i或者从i出发的边
       //如果出现tt时刻的询问则查询最短路
       for(int i=0;i<n;i++)
       {
           if(t[i]<=tt)
           {

               //在tt时刻则说明重建时间小于tt的所有村庄都建好了
               //其中最大的tt[i]的村庄编号为i
               for(int x=0;x<=i;x++)
                   for(int y=0;y<=i;y++)
                   {
                       midG[x][y]=G[x][y];
                       midG[y][x]=G[y][x];
                   }
           }
       }
       //查询在tt时刻是否有存在询问
       for(int i=0;i<Q;i++)
       {
           if(Ques[i].ttt==tt)
           {
               int start=Ques[i].u;
               int end  =Ques[i].v;
               //执行dijsktra
               int ans=dijsktra(start,end);
               cout<<ans<<endl;
           }
       }
   }
   return 0;
}
//为什么连样例都没过只有一个没过了