微信网站技术方案,深圳市南山网站建设,做外销网站,注册个体工商户用于网站建设题目背景
B 地区在地震过后#xff0c;所有村庄都造成了一定的损毁#xff0c;而这场地震却没对公路造成什么影响。但是在村庄重建好之前#xff0c;所有与未重建完成的村庄的公路均无法通车。换句话说#xff0c;只有连接着两个重建完成的村庄的公路才能通车#xff0c;…题目背景
B 地区在地震过后所有村庄都造成了一定的损毁而这场地震却没对公路造成什么影响。但是在村庄重建好之前所有与未重建完成的村庄的公路均无法通车。换句话说只有连接着两个重建完成的村庄的公路才能通车只能到达重建完成的村庄。
题目描述
给出 B 地区的村庄数 N村庄编号从 0 到 N−1和所有 M 条公路的长度公路是双向的。并给出第 i 个村庄重建完成的时间 ti你可以认为是同时开始重建并在第 ti 天重建完成并且在当天即可通车。若 ti 为 0 则说明地震未对此地区造成损坏一开始就可以通车。之后有 Q 个询问 (x,y,t)对于每个询问你要回答在第 t 天从村庄 x 到村庄 y 的最短路径长度为多少。如果无法找到从 x 村庄到 y 村庄的路径经过若干个已重建完成的村庄或者村庄 x 或村庄 y 在第 t 天仍未重建完成则需要输出 −1。
输入格式
第一行包含两个正整数 N,M表示了村庄的数目与公路的数量。
第二行包含 N 个非负整数 t0,t1,⋯,tN−1表示了每个村庄重建完成的时间数据保证了 t0≤t1≤⋯≤tN−1。
接下来 M 行每行 3 个非负整数 i,j,ww 为不超过 10000 的正整数表示了有一条连接村庄 i 与村庄 j 的道路长度为 w保证 j≠i且对于任意一对村庄只会存在一条道路。
接下来一行也就是 M3 行包含一个正整数 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。
输入输出样例
输入 #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
-1
5
4
说明/提示
对于 30% 的数据有 N≤50对于 30% 的数据有 ti0其中有 20% 的数据有 ti0 且 N50对于 50% 的数据有 Q≤100对于 100% 的数据有 1≤N≤20020≤M≤2N×(N−1)1≤Q≤50000所有输入数据涉及整数均不超过 105。
解析
这题一看就是图论的问题阅读完题目后村庄的修建时间是不减递增的。后面的询问时间也是递增的。
在联想到最短路问题有Floyd算法可以很快的求出最短路径其数据也没有那么大。
这是一道不错的Floyd算法的运用。
普通的Floyd算法是三层for循环dp[i][j] min(dp[i][k],dp[k][j],dp[i][j]);
for(k1;kn;k)for(i1;in;i)for(j1;jn;j)if(e[i][j]e[i][k]e[k][j])e[i][j]e[i][k]e[k][j];
从i地点到k,在从k到达j。
所有的边全部给出按照时间顺序更新每一个可用的点即修建好村庄对于每个时间点进行两点之间询问求对于目前建设的所有村庄来说任意两点之间的最短路
不正好就是Floyd算法中使用前k个节点更新最短路的思维吗
核心代码
inline void updata(int k){ //以k为中心的点进行更新for(int i 0;i n;i){for(int j 0;j n;j){if(f[i][j] f[i][k] f[j][k]){f[i][j] f[j][i] f[i][k] f[k][j];}}}return;
}
代码
#includebits/stdc.h
using namespace std;
#define N 205
#define endl \n
int n,m;
int a[N];
int f[N][N];
inline void updata(int k){for(int i 0;i n;i){for(int j 0;j n;j){if(f[i][j] f[i][k] f[j][k]){f[i][j] f[j][i] f[i][k] f[k][j];}}}return;
}
int main()
{cin n m;for(int i 0;i n;i){scanf(%d,ai);}for(int i 0;i n;i){ //初始化 for(int j 0;j n;j){f[i][j] 1e9;}}for(int i 0;i n;i) {f[i][i] 0;}int s1,s2,s3;for(int i 1;i m;i){ //从s1 - s2 的距离 scanf(%d%d%d,s1,s2,s3);f[s1][s2] f[s2][s1] s3;}int q;cin q;int now 0;for(int i 1;i q;i){scanf(%d%d%d,s1,s2,s3);while(a[now] s3 now n){ //now是指遍历到那个节点 updata(now);now;}if(a[s1] s3||a[s2] s3) cout -1endl;else{if(f[s1][s2] 1e9) cout -1 endl;else cout f[s1][s2] endl;}}return 0;
}
//4 5
//1 3 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
