当前位置：首页 > news >正文

ch06 部分题目思路

news 2025/7/12 15:50:39

D. 异地

仅需在最短路算法中，希望使用 d[u]+w 松弛 d[v] 时，把 du 替换 >= du 的 k 的倍数的最小值即可

using ll = long long;
const int maxn = 100010;
struct edge {int v, t, k;ll w;  // 最短路bool operator<(const edge &e) const { return w > e.w; }
};
vector<edge> G[maxn];
ll d[maxn];
int n;
priority_queue<edge> q;
void dij(int s) {memset(d, 0x3f, sizeof(d));d[s] = 0;q.push({s, 0});while (!q.empty()) {edge e = q.top();int u = e.v;q.pop();if (e.w > d[u]) continue;for (int i = 0; i < G[u].size(); ++i) {int v = G[u][i].v, k = G[u][i].k, t = G[u][i].t;// 需要从 du 开始等到 k 的倍数出发ll du = (d[u] + k - 1) / k * k;if (d[v] > du + t) {d[v] = du + t;q.push({v, t, k, d[v]});}}}return;
}
int main() {// s 为单源最短路的源点int m, u, v, t, k, x, y;cin >> n >> m >> x >> y;for (int i = 0; i < m; ++i) {cin >> u >> v >> t >> k;G[u].push_back({v, t, k, 0});G[v].push_back({u, t, k, 0});}dij(x);if (d[y] == 0x3f3f3f3f3f3f3f3f) cout << -1 << endl;else cout << d[y] << endl;return 0;
}

F. 滑雪

把（幸福感 * -1）设为边权，求 1 出发能获得最大幸福感，等价于求图上的最短路长度 * -1

此时边权有负权，跑 SPFA 算法，部分样例会超时，可拿大部分分数（98分）。

继续优化时间：

建边时，对所有的边（u -> v），加上 h[u] - h[v]，此时边权全为非负。
在新图上，路径 1(x0) -> x1 -> x2 -> x3 -> xk 的边权和就变成
- (w1+h[1]-h[x1]) + (w2+h[x1]-h[x2]) + (w3+h[x3]-h[x2]) + ...
- = w1 + w2 + ... + wk + h[1] - h[k]
所以以 1 为起点跑 Dijkstra 算法，此时 d[u] = 1 到 u 的最短路 + h[1] - h[u]
最终答案在所有 -(d[u] - h[1] + h[u]) 中，取最大值即可

#include <bits/stdc++.h>
using namespace std;using ll = long long;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int maxn = 200010;
struct Edge {int v, w;
};
vector<Edge> G[maxn];
struct Node {int u;ll d;bool operator<(const Node &n) const { return d > n.d; }
};
ll d[maxn];
bool vis[maxn];void Dij(int s) {// 一定要初始化memset(d, 0x3f, sizeof(d));priority_queue<Node> pq;d[s] = 0, pq.push({s, d[s]});while (!pq.empty()) {int u = pq.top().u;pq.pop();// u 可以进入 pq 多次，只取第一次if (vis[u]) continue;vis[u] = 1;for (Edge e : G[u]) {int v = e.v, w = e.w;if (d[v] > d[u] + w) {d[v] = d[u] + w;pq.push({v, d[v]});}}}
}// ---------------- 以上为最短路模板int h[maxn];
int main() {int n, m;cin >> n >> m;for (int i = 1; i <= n; ++i) cin >> h[i];// 输入格式：a[i] b[i] x[i]for (int i = 0; i < m; ++i) {int u, v;cin >> u >> v;if (h[u] < h[v]) swap(u, v);G[u].push_back({v, 0});G[v].push_back({u, h[u] - h[v]});}Dij(1);ll res = 0;for (int i = 1; i <= n; ++i) {// if (d[i] == inf) continue; // 题目保证连通// d[i] = sumW + h[1] - h[i]ll sumW = d[i] - h[1] + h[i];res = max(res, -sumW);}cout << res << "\n";return 0;
}