Editorial for Bedao OI Contest 3 - Quán trà sữa
Submitting an official solution before solving the problem yourself is a bannable offence.
Subtask 1
Duyệt mọi ngôi nhà ~u~ và tìm đường đi ngắn nhất tới các ngôi nhà còn lại, đáp án sẽ là khoảng cách ngắn nhất từ ~u~ tới ~p_i~ (~1 \le i \le k~).
Subtask 2
Sử dụng thuật toán Dijkstra đi từ các quán trà sữa tới mọi căn nhà còn lại, với ~d_i~ là đường đi ngắn nhất từ một quán trà sữa bất kì tới ~i~. Vì ~t_i = 0~ nên với những nhà tự mở quán thì ~d_i = 0~.
Subtask 3
Với điều kiện ràng buộc là cây, ta có thể quy hoạch động trên cây, với ~dp_{child}[u]~ là khoảng cách từ quán trà sữa gần nhất nào đó trong cây con gốc ~u~ tới ~u~, và ~dp_{par}[u]~ là khoảng cách từ quán trà sữa gần nhất nào đó phải đi qua ~par[u]~ tới ~u~.
Đáp án với mỗi đỉnh ~u~ sẽ là ~min(dp_{child}[u], dp_{par}[u])~.
Subtask 4
Cũng dựa vào Subtask 2 nhưng ta cần tìm quán trà sữa gần nhất cho các quán có ~t_i = 1~. Lúc này, ~d_i~ sẽ lưu ~2~ khoảng cách ngắn nhất từ ~2~ quán trà sữa khác nhau bất kì tới ~i~. Với những ngôi nhà có quán và ~t_i = 1~ thì đáp án sẽ là khoảng cách ngắn thứ ~2~ sau khoảng cách ngắn nhất bằng ~0~ do uống ở nhà.
#include <bits/stdc++.h> #define ll long long #define pa pair<ll, int> #define fi first #define se second using namespace std; const int N = 1e5+5; const ll oo = 1e18; int n, m, k; vector<pa> adj[N]; bool milktea[N], findNew[N]; ll d[2][N]; int origin[2][N]; void Dijkstra() { priority_queue<pa, vector<pa>, greater<pa> > pq; for (int i = 1; i <= n; i++) { d[0][i] = d[1][i] = oo; if (milktea[i]) { d[0][i] = 0, origin[0][i] = i; pq.emplace(0, i); } } ll dist, tempDist; int node, root, far; while(!pq.empty()) { tie(dist, node) = pq.top(); pq.pop(); if (node > n) far = 1, node -= n; else far = 0; if (dist != d[far][node]) continue; root = origin[far][node]; for (auto x: adj[node]) { tempDist = dist + x.fi; if (!far && d[0][x.se] > tempDist) { if (origin[0][x.se] != root) { origin[1][x.se] = origin[0][x.se]; d[1][x.se] = d[0][x.se]; pq.emplace(d[1][x.se], x.se + n); } origin[0][x.se] = root; d[0][x.se] = tempDist; pq.emplace(d[0][x.se], x.se); } else if (d[1][x.se] > tempDist && origin[0][x.se] != root) { origin[1][x.se] = root; d[1][x.se] = tempDist; pq.emplace(d[1][x.se], x.se + n); } } } } int main() { cin.tie(0) -> sync_with_stdio(0); freopen("milktea.inp", "r", stdin); freopen("milktea.out", "w", stdout); cin >> n >> m >> k; assert(2 <= k && k <= n); for (int i = 1, u, v, w; i <= m; i++) { cin >> u >> v >> w; adj[u].emplace_back(w, v); adj[v].emplace_back(w, u); } for (int i = 1, x; i <= k; i++) { cin >> x; milktea[x] = 1; cin >> findNew[x]; } Dijkstra(); for (int i = 1; i <= n; i++) { if (!milktea[i] || !findNew[i]) cout << d[0][i] << ' '; else cout << d[1][i] << ' '; // cerr << i << endl; // cerr << d[0][i] << ' ' << origin[0][i] << endl; // cerr << d[1][i] << ' ' << origin[1][i] << endl; } return 0; }
Comments