题面
B地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。
给出B地区的村庄数N，村庄编号从0到N−1，和所有M条公路的长度，公路是双向的。并给出第i个村庄重建完成的时间你可以认为是同时开始重建并在第\(t_i\)
天重建完成，并且在当天即可通车。若\(t_i\)
为0则说明地震未对此地区造成损坏，一开始就可以通车。之后有Q个询问\((x, y, t)\)，对于每个询问你要回答在第t天，从村庄x到村庄y的最短路径长度为多少。如果无法找到从x村庄到y村庄的路径，经过若干个已重建完成的村庄，或者村庄x或村庄y在第t天仍未重建完成 ，则需要返回-1。
t是不下降的
解：
魔改floyd
发现n<=200 考虑用floyd
关键是怎么考虑魔改
注意到floyd的公式是$ f[i][j]=f[i][k]+f[k][j]$ 那么只要控制中转点更新最优值 我们就能求出答案
时间复杂度 \(O(q*n^2)\)
code：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mapp1[500][500];
int n,m;
typedef pair<int ,int > P;
set<P> Q;
set<int> K;
int tot=0;
int q;
set<P> :: iterator it;
int main(){
//freopen("%","r",stdin);
// freopen("%","w",stdout);
cin>>n>>m;
int x,y,z;
for(int i=1;i<=n;i++)
{
cin>>x;
Q.insert(make_pair(x,i));
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
mapp1[i][j]=1e10;
if(i==j)
{
mapp1[i][j]=0;
}
}
for(int i=1;i<=m;i++)
{
cin>>x>>y>>z;
x++;
y++;
mapp1[x][y]=z;
mapp1[y][x]=z;
}
cin>>q;
while(q--)
{
cin>>x>>y>>z;
if(Q.size())
{
it=Q.begin();
while(Q.size()&&(*it).first<=z)
{
Q.erase(it);
int k=(*it).second;
K.insert((*it).second);
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
if(mapp1[i][j]>mapp1[i][k]+mapp1[k][j])
{
mapp1[i][j]=mapp1[i][k]+mapp1[k][j];
}
}
}
if(Q.size())
it=Q.begin();
}
}
if(mapp1[x+1][y+1]==1e10||K.find(x+1)==K.end()||K.find(y+1)==K.end())
cout<<-1<<endl;
else
cout<<mapp1[y+1][x+1]<<endl;
}
}