网站运营意义,网络运维培训,商丘高端网站建设,设计师网站都有哪些原题链接#xff1a;
灾后重建 - 洛谷 题目大意#xff1a;
有n个村庄#xff0c;村庄间有m条公路#xff0c;一次地震将连向每个村庄的公路损坏#xff0c;所以要进行维修#xff0c;数据保证编号小的村庄维修时间更少#xff0c;编号大的村庄维修时间更多。后面有q个…原题链接
灾后重建 - 洛谷 题目大意
有n个村庄村庄间有m条公路一次地震将连向每个村庄的公路损坏所以要进行维修数据保证编号小的村庄维修时间更少编号大的村庄维修时间更多。后面有q个询问问是在第几天的时候从x村庄到y村庄我们是否能到达如果能到达的最小距离是多少。 解题思路
题目数据给出的是一个稠密图最大可以是一个全连通图每两个点之间都有边直连。
最朴素的想法是每读一个查询就对整个新图重新跑一次dijkstra复杂为O(Q*m*n*logn)O(Q*n^3*logn)如果换成floyd复杂度为O(Q*n^3)更好但依然超时。
其实我们可以只需要完整的进行一次floyd而不需要Q次总的复杂度为O(Qn^3)。
因为每个顶点的修复时间是按顶点编号递增的floyd的执行过程又是逐步加入点从第1个点扩展到第n个点加第k个点时前面的1~k-1个点都已经执行完毕当k到达最后的第n个点时包含所有1~n点的最短路径计算完毕。而在本题在第t个时刻小于t时刻的图的顶点的最短路径计算完毕在t1时刻只需要在t时刻计算结果的基础上继续计算新加入的点(t~t1时间内修复的村庄)即可。 代码CPP
#include bits/stdc.h
using namespace std;
#define endl \n
typedef long long ll;
typedef unsigned long long ull;
const int maxn 310;
const int INF 0x3fffffff;
const int mod 1000000007;
struct edge {int v, w;
};
int dis[maxn][maxn];
int t[maxn];
int n, m;/*题目数据给出的是一个稠密图最大可以是一个全连通图每两个点之间都有边直连。最朴素的想法是每读一个查询就对整个新图重新跑一次dijkstra复杂度为O(Q*m*n*logn)O(Q*n^3*logn),如果换成floyd复杂度为O(Q*n^3)更好但依然超时。其实我们可以只需要完整的进行一次floyd而不需要Q次总的复杂度为O(Qn^3)。因为每个顶点的修复时间是按顶点编号递增的floyd的执行过程又是逐步加入点从第1个点扩展到第n个点加第k个点时前面的1~k-1个点都已经执行完毕当k到达最后的第n个点时包含所有1~n点的最短路径计算完毕。而在本题在第t个时刻小于t时刻的图的顶点的最短路径计算完毕在t1时刻只需要在t时刻计算结果的基础上继续计算新加入的点(t~t1时间内修复的村庄)即可。
*/void solve() {cin n m;for (int i 0; i n; i) {cin t[i];}for (int i 0; i n; i){for (int j 0; j n; j) {if (i ! j)dis[i][j] dis[j][i] INF;}}while (m--) {int u, v, w;cin u v w;dis[u][v] dis[v][u] w;}int q;cin q;int k 0;while (q--) {int u, v, tt;cin u v tt;for (; k n t[k] tt; k) { // 将t~t1时刻内修复的点的计算出来for (int i 0; i n; i) {for (int j 0; j n; j) {if (dis[i][k] ! INF dis[k][j] ! INF dis[i][k] dis[k][j] dis[i][j]) {dis[i][j] dis[i][k] dis[k][j];}}}}if (dis[u][v] INF || t[u] tt || t[v] tt) {cout -1 endl;} else {cout dis[u][v] endl;}}
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout fixed;cout.precision(18);solve();return 0;
}