目录
- 题面
- 题目链接
- 题目描述
- 输入输出格式
- 输入格式
- 输出格式
- 输入输出样例
- 输入样例
- 输出样例
- 说明
- 思路
- AC代码
- 总结
题面
题目链接
P1119 灾后重建
题目描述
B地区在地震过后，所有村庄都造成了一定的损毁，而这场地震却没对公路造成什么影响。但是在村庄重建好之前，所有与未重建完成的村庄的公路均无法通车。换句话说，只有连接着两个重建完成的村庄的公路才能通车，只能到达重建完成的村庄。
给出B地区的村庄数 $ N $ ，村庄编号从 $ 0 $ 到 $ N−1 $ ，和所有 $ M $ 条公路的长度，公路是双向的。并给出第 $ i $ 个村庄重建完成的时间 $ t_i $ ，你可以认为是同时开始重建并在第 $ t_i $ 天重建完成，并且在当天即可通车。若 $ t_i $ 为 $ 0 $ 则说明地震未对此地区造成损坏，一开始就可以通车。之后有 $ Q $ 个询问 $ (x,y,t) $ ，对于每个询问你要回答在第 $ t $ 天，从村庄 $ x $ 到村庄 $ y $ 的最短路径长度为多少。如果无法找到从 $ x $ 村庄到 $ y $ 村庄的路径，经过若干个已重建完成的村庄，或者村庄 $ x $ 或村庄 $ y $ 在第t天仍未重建完成 ，则需要返回 $ -1 $ 。
输入输出格式
输入格式
第一行包含两个正整数 $ N,M $ ，表示了村庄的数目与公路的数量。
第二行包含 N 个非负整数 $ t_0, t_1,…, t_{N-1} $ ，表示了每个村庄重建完成的时间，数据保证了 $ t_0 \leq t_1 \leq ... \leq t_{N-1} $
接下来 $ M $ 行，每行 $ 3 $ 个非负整数 $ i,j,w $ ， $ w $ 为不超过 $ 10000 $ 的正整数，表示了有一条连接村庄 $ i $ 与村庄 $ j $ 的道路，长度为 $ w $ ，保证 $ i≠j $，且对于任意一对村庄只会存在一条道路。
接下来一行也就是 $ M+3 $ 行包含一个正整数 $ Q $ ，表示 $ Q $ 个询问。
接下来 $ Q $ 行，每行 $ 3 $ 个非负整数 $ x,y,t $ ，询问在第 $ t $ 天，从村庄 $ x $ 到村庄 $ y $ 的最短路径长度为多少，数据保证了 $ t $ 是不下降的。
输出格式
共 $ Q $ 行，对每一个询问 $ (x,y,t) $ 输出对应的答案，即在第 $ t $ 天，从村庄 $ x $ 到村庄 $ y $ 的最短路径长度为多少。如果在第 $ t $ 天无法找到从 $ x $ 村庄到 $ y $ 村庄的路径，经过若干个已重建完成的村庄，或者村庄 $ x $ 或村庄 $ y $ 在第 $ t $ 天仍未修复完成，则输出 $ -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%的数据，有 $ N \leq 50 $；
对于30%的数据，有 $ t_i=0 $ ，其中有 20% 的数据有 $ t_i=0 $ 且 $ N>50 $ ；
对于50%的数据，有 $ Q \leq 100 $ ；
对于100%的数据，有 $ N≤200 $ ，$ M \leq N \times (N-1) / 2 $ ， $ Q \leq 50000 $ ，所有输入数据涉及整数均不超过 100000 。
【时空限制】
1000ms,128M
思路
首先看到要多次询问两点间的最短路，可以考虑用Floyd算法。可是两点间的距离是随着时间而变化的，怎么办呢？
显然我们可以这样做：当每次询问时，我们将此时已经修建好的村庄之间跑一遍Floyd，其他村庄不管。但是这样做肯定会TLE。
想想怎么优化。注意到询问时 $ t_i $ 是递增的，村庄修建好的顺序也是递增的，那么我们可以记录一个当前修建好的村庄的最大编号。每次询问时，看是否有新的村庄修好了，如果有，那么把他加进来作为中转点跑一次最短路
AC代码
#include<bits/stdc++.h>
const int maxn=210;
using namespace std;int n,m,T[maxn];
int Q,np;
int dis[maxn][maxn];int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++) scanf("%d",&T[i]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) if(i!=j)dis[i][j]=INT_MAX/2;for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);u++;v++;dis[u][v]=min(dis[u][v],w);dis[v][u]=min(dis[v][u],w);}scanf("%d",&Q);np=1;for(int i=1;i<=Q;i++){int u,v,t;scanf("%d%d%d",&u,&v,&t);u++,v++;for(np;T[np]<=t && np<=n;np++){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=min(dis[i][j],dis[i][np]+dis[np][j]);}if(T[u]<=t && T[v]<=t && dis[u][v]!=INT_MAX/2) printf("%d\n",dis[u][v]);else printf("-1\n");}return 0;
}总结
优化的这一步可以说题目也提示了很多。如果题中没有给递增条件，也许我就不会做了。