这道题我们很容易想到对于每次询问，都跑一遍最短路（spfa，虽然他已经死了）。只需在松弛的时候加入当前相关的点是否已经修好的判断，果不其然的TLE了4个点。
（然鹅我第一次用spfa跑的时候竟然全WA了，震惊！由于节点从0开始标号，所以head数组要预处理为-1，遍历的时候for(int i=head[x];i!=-1;i=edge[i].next啊啊啊啊啊）
Code_TLE
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue> using namespace std;
const int inf=; int n,m,Q,tot;
int ddl[],dis[],head[];
bool vis[];
struct node{
int next,to,val;
}edge[]; void add(int x,int y,int z)
{
edge[++tot].to=y;
edge[tot].val=z;
edge[tot].next=head[x];
head[x]=tot;
} int spfa_ask(int s,int t,int T)
{
memset(vis,,sizeof(vis));
for(int i=;i<n;i++) dis[i]=inf;
queue<int>q;
q.push(s);dis[s]=;vis[s]=;
while(!q.empty())
{
int x=q.front();
q.pop();vis[x]=;
for(int i=head[x];i!=-;i=edge[i].next)
{
int y=edge[i].to;
if(dis[y]>dis[x]+edge[i].val&&ddl[y]<=T&&ddl[x]<=T)
{
dis[y]=dis[x]+edge[i].val;
if(!vis[y]) q.push(y),vis[y]=;
}
}
}
if(dis[t]==inf) dis[t]=-;
return dis[t];
} int main()
{
memset(head,-,sizeof(head));
scanf("%d%d",&n,&m);
for(int i=;i<n;i++) scanf("%d",&ddl[i]);
for(int i=;i<=m;i++)
{
int x=,y=,z=;
scanf("%d%d%d",&x,&y,&z);
add(x,y,z);add(y,x,z);
}
scanf("%d",&Q);
while(Q--)
{
int x=,y=,T=;
scanf("%d%d%d",&x,&y,&T);
printf("%d\n",spfa_ask(x,y,T));
}
return ;
}
万万没想到，正解竟然是--floyd!
其实看似繁琐的题目已经隐藏着真相--
本题的数据范围n<=200，这对于最短路题目来说是十分超常友善的：）也正暗喻着本题floyd才是正解。
正解：
我们考虑floyd的算法，本质是一个动态规划，最外层枚举中心点，注意到每次询问的时间有单调性，那么我们可以每次把两次询问间新建出的村庄的floyd跑好得出答案。
看题解在这卡了很久，结果发现自己忽略了一个条件：输入村庄的修复时间也是有单调性的，有了这个条件一切不就顺理成章了嘛。
Code
#include<cstdio>
#include<cstring>
#include<algorithm> using namespace std; int n,m,Q,pos,limit;
int ddl[];
int f[][]; int main()
{
scanf("%d%d",&n,&m);
memset(f,0x3f,sizeof(f));
limit=f[][];
for(int i=;i<n;i++) scanf("%d",&ddl[i]),f[i][i]=;
for(int i=;i<=m;i++)
{
int x=,y=,z=;
scanf("%d%d%d",&x,&y,&z);
f[x][y]=z;f[y][x]=z;
}
scanf("%d",&Q);
while(Q--)
{
int x=,y=,t=;
scanf("%d%d%d",&x,&y,&t);
if(ddl[x]>t||ddl[y]>t)
{
printf("-1\n");
continue;
}
while(ddl[pos]<=t&&pos<n)
{
for(int i=;i<n;i++)
for(int j=;j<n;j++)
f[i][j]=min(f[i][j],f[i][pos]+f[pos][j]);
pos++;
}
if(f[x][y]==limit)
{
printf("-1\n");
continue;
}
printf("%d\n",f[x][y]);
}
return ;
}
审题！审题！别丢条件！