1 条题解
-
0
30 分
所有边海拔相同时，答案要么是 （所有边都没被淹没），要么是 （所有边都被淹没了，只能步行）
#include <bits/stdc++.h> using namespace std; const int MAXN = 200000; const int MAXM = 400000; const int INF = 2'000'000'000 + 1; int n, m; // e[u] 存所有起点为 u 的边 <终点,<长度,海拔>> vector<pair<int, pair<int, int>>> e[MAXN + 5]; // 1 号点为起点的 dijkstra int dis[MAXN + 5]; bool vis[MAXN + 5]; priority_queue<pair<int, int>> pq; void dijkstra() { for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = false; dis[1] = 0; pq.push({-0, 1}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = true; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i].first; int l = e[u][i].second.first; // 长度 int a = e[u][i].second.second; // 海拔 if (vis[v]) continue; if (dis[v] > dis[u] + l) { dis[v] = dis[u] + l; pq.push({-dis[v], v}); } } } } void work() { cin >> n >> m; for (int i = 1; i <= n; i++) e[i].clear(); for (int i = 1; i <= m; i++) { int u, v, l, a; cin >> u >> v >> l >> a; e[u].push_back({v, {l, a}}); e[v].push_back({u, {l, a}}); } dijkstra(); int Q, K, S; cin >> Q >> K >> S; int lastAns = 0; while (Q--) { int v0, p0; cin >> v0 >> p0; v0 = (v0 + K * lastAns - 1) % n + 1; p0 = (p0 + K * lastAns) % (S + 1); if (p0 >= 1) { lastAns = dis[v0]; cout << dis[v0] << "\n"; } else { lastAns = 0; cout << 0 << "\n"; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) work(); return 0; }55 分
每个询问暴力搜索找到能到达的 dis 最小的点
#include <bits/stdc++.h> using namespace std; const int MAXN = 200000; const int MAXM = 400000; const int INF = 2'000'000'000 + 1; int n, m; // e[u] 存所有起点为 u 的边 <终点,<长度,海拔>> vector<pair<int, pair<int, int>>> e[MAXN + 5]; // 1 号点为起点的 dijkstra int dis[MAXN + 5]; bool vis[MAXN + 5]; priority_queue<pair<int, int>> pq; void dijkstra() { for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = false; dis[1] = 0; pq.push({-0, 1}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = true; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i].first; int l = e[u][i].second.first; // 长度 int a = e[u][i].second.second; // 海拔 if (vis[v]) continue; if (dis[v] > dis[u] + l) { dis[v] = dis[u] + l; pq.push({-dis[v], v}); } } } } // 从 u 出发，海拔为 p 时能到的点中的 dis 的最小值 int numNow, numVis[MAXN + 5]; int dfs(int u, int p) { numVis[u] = numNow; int ans = dis[u]; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i].first; int l = e[u][i].second.first; int a = e[u][i].second.second; if (a <= p) continue; if (numVis[v] == numNow) continue; ans = min(ans, dfs(v, p)); } return ans; } void work() { cin >> n >> m; for (int i = 1; i <= n; i++) e[i].clear(); bool flag30 = true; for (int i = 1; i <= m; i++) { int u, v, l, a; cin >> u >> v >> l >> a; e[u].push_back({v, {l, a}}); e[v].push_back({u, {l, a}}); if (a != 1) flag30 = false; } dijkstra(); int Q, K, S; cin >> Q >> K >> S; int lastAns = 0; while (Q--) { int v0, p0; cin >> v0 >> p0; v0 = (v0 + K * lastAns - 1) % n + 1; p0 = (p0 + K * lastAns) % (S + 1); if (flag30) { if (p0 >= 1) lastAns = dis[v0]; else lastAns = 0; cout << lastAns << "\n"; } else { numNow++; lastAns = dfs(v0, p0); cout << lastAns << "\n"; } } } int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) work(); return 0; }100 分
实际上求
lca(u,v)的部分是不用的，但是懒得删了。#include <bits/stdc++.h> using namespace std; const int MAXN = 200000; const int MAXM = 400000; const int INF = 2'000'000'000 + 1; int n, m; // e[u] 存所有起点为 u 的边 <终点,<长度,海拔>> vector<pair<int, pair<int, int>>> e[MAXN + 5]; // 1 号点为起点的 dijkstra int dis[MAXN * 2 + 5]; // 后续会重复利用为 kruskal 生成树的节点答案 bool vis[MAXN + 5]; priority_queue<pair<int, int>> pq; void dijkstra() { for (int i = 1; i <= n; i++) dis[i] = INF, vis[i] = false; dis[1] = 0; pq.push({-0, 1}); while (!pq.empty()) { int u = pq.top().second; pq.pop(); if (vis[u]) continue; vis[u] = true; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i].first; int l = e[u][i].second.first; // 长度 int a = e[u][i].second.second; // 海拔 if (vis[v]) continue; if (dis[v] > dis[u] + l) { dis[v] = dis[u] + l; pq.push({-dis[v], v}); } } } } // Kruskal 重构树 // 并查集 int fa[MAXN * 2 + 5]; int findFa(int x) { if (x == fa[x]) return x; return fa[x] = findFa(fa[x]); } // 存边 <-权值,<起点,终点>> vector<pair<int, pair<int, int>>> ee; // 封装 LCA（kruskal 版本，节点数量 2*n） namespace LCA { int w[MAXN * 2 + 5]; // 节点对应边权 int n, m, s; vector<int> e[MAXN * 2 + 5]; // f[i][j] 记录 i 的 2^j 级别祖先 int f[MAXN * 2 + 5][25]; // dep[i] 求节点 i 的深度 int dep[MAXN * 2 + 5]; void clear(int n) { for (int i = 1; i <= n; i++) e[i].clear(); } void addEdge(int u, int v) { e[u].push_back(v); e[v].push_back(u); } void dfs(int u, int fa) { f[u][0] = fa; for (int i = 0; i < e[u].size(); i++) { int v = e[u][i]; if (v == fa) continue; dep[v] = dep[u] + 1; dfs(v, u); } } void init() { dep[s] = 0; dfs(s, 0); // 预处理深度 dep[u]，以及一级祖先 f[u][0] // i 的 2^j 级别祖先 = i 的 2^{j-1} 级别祖先的 2^{j-1} 级别祖先 for (int j = 1; (1LL << j) <= n; j++) for (int i = 1; i <= n; i++) f[i][j] = f[f[i][j - 1]][j - 1]; } int lca(int u, int v) { // 保证 u 在上面，v 在下面 if (dep[v] < dep[u]) swap(u, v); // 拉到同样的深度 for (int j = 20; j >= 0; j--) if (dep[v] - dep[u] >= (1 << j)) v = f[v][j]; // 初始两点之间是祖孙关系时，拉到同样深度就会变成同一个点 if (u == v) return u; // 同步往上走，跳到了 lca 下面一跳位 for (int j = 20; j >= 0; j--) if (f[u][j] != f[v][j]) u = f[u][j], v = f[v][j]; return f[u][0]; } } void work() { cin >> n >> m; for (int i = 1; i <= n; i++) e[i].clear(); ee.clear(); for (int i = 1; i <= m; i++) { int u, v, l, a; cin >> u >> v >> l >> a; e[u].push_back({v, {l, a}}); e[v].push_back({u, {l, a}}); ee.push_back({-a, {u, v}}); } dijkstra(); // kruskal 重构树 for (int i = 1; i <= 2 * n; i++) fa[i] = i; sort(ee.begin(), ee.end()); LCA::n = n; LCA::clear(2 * n); for (int i = 0; i < ee.size(); i++) { int w = -ee[i].first; int u = ee[i].second.first; int v = ee[i].second.second; int faU = findFa(u); int faV = findFa(v); if (faU == faV) continue; LCA::n++; fa[faU] = fa[faV] = LCA::n; // 新建节点的答案设置为两个子树的 dis 较小值 dis[LCA::n] = min(dis[faU], dis[faV]); // 新建节点海拔设置为边的海拔 LCA::w[LCA::n] = w; LCA::addEdge(LCA::n, faU); LCA::addEdge(LCA::n, faV); } // LCA 预处理 LCA::s = LCA::n; LCA::init(); int Q, K, S; cin >> Q >> K >> S; int lastAns = 0; while (Q--) { int v0, p0; cin >> v0 >> p0; v0 = (v0 + K * lastAns - 1) % n + 1; p0 = (p0 + K * lastAns) % (S + 1); // 找到最合适的祖宗节点 for (int i = 20; i >= 0; i--) { if (LCA::w[LCA::f[v0][i]] > p0) v0 = LCA::f[v0][i]; } // 输出对应答案 lastAns = dis[v0]; cout << lastAns << "\n"; } } int main() { ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) work(); return 0; }
- 1
