Solutions of Festival 2 - MarisaOJ: Marisa Online Judge

Solutions of Festival 2

Select solution language

Write solution here.


ducyn    Created at    1 likes

**Hint:** Ta cần chọn một cạnh $(u, v)$ sao cho **tổng khoảng cách từ tất cả các điểm đặc biệt tới cạnh đó** là nhỏ nhất. Khoảng cách từ một điểm đặc biệt $p_i$ tới cạnh $(u, v)$ được tính là: $$ \min\big( dist(p_i, u),\ dist(p_i, v) \big) $$ trong đó `dist(a, b)` là khoảng cách ngắn nhất giữa hai đỉnh. --- **Các bước thực hiện:** 1. **Đọc dữ liệu và xây dựng đồ thị** dưới dạng danh sách kề. 2. **Tính khoảng cách từ mỗi điểm đặc biệt tới mọi đỉnh**: * Dùng BFS xuất phát từ từng điểm đặc biệt. * Lưu kết quả vào mảng `dp[i][v]` = khoảng cách từ điểm đặc biệt thứ `i` đến đỉnh `v`. 3. **Duyệt tất cả các cạnh** $(u, v)$: * Với mỗi điểm đặc biệt, lấy khoảng cách ngắn nhất tới $u$ hoặc $v$. * Cộng dồn các khoảng cách lại thành tổng `sum`. * Bỏ qua cạnh nếu có điểm đặc biệt không thể tới cả hai đầu của cạnh. 4. **Tìm giá trị nhỏ nhất của tổng** và in kết quả. --- **Độ phức tạp:** * BFS từ mỗi điểm đặc biệt: $O(k \cdot (n+m))$ * Duyệt tất cả các cạnh để tính tổng: $O(m \cdot k)$ * Tổng thời gian: $O(k \cdot (n+m))$, đủ nhanh với $n, m \le 3000$. --- Code tham khảo: ```cpp #include <bits/stdc++.h> #define ll long long #define name "TASK" #define TIME (1.0 * clock() / CLOCKS_PER_SEC) using namespace std; const int MAXN=3005; int n, m, k, p[MAXN], d[MAXN]; vector<int> adj[MAXN]; int dp[MAXN][MAXN]; void inp(){ cin>>n>>m>>k; for(int i=0;i<k;i++){ cin>>p[i]; } for(int i=0;i<m;i++){ int u, v; cin>>u>>v; adj[u].push_back(v); adj[v].push_back(u); } memset(d, -1, sizeof(d)); } void bfs(int u, int idx){ memset(d, -1, sizeof(d)); queue<int> q; d[u] = 0; q.push(u); while(!q.empty()){ int t=q.front(); q.pop(); for(int v:adj[t]){ if(d[v] == -1){ d[v]=d[t]+1; q.push(v); } } } for(int v=1; v<=n;v++) dp[idx][v]=d[v]; } void solve(){ inp(); int res=INT_MAX; for (int i=0; i<k;i++) { bfs(p[i], i); } for(int u=1;u<=n;u++) { for(int v : adj[u]) { if (u < v) { int sum = 0; bool c = false; for(int i=0;i<k;i++){ int du=dp[i][u], dv=dp[i][v]; if (du==-1 && dv==-1) { c=true; break; } int best=(du == -1 ? dv : (dv == -1 ? du : min(du, dv))); sum += best; if(sum >= res) break; } if(!c) res=min(res, sum); } } } cout<<res<<'\n'; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if(fopen(name".INP","r")) { freopen(name ".INP","r",stdin); freopen(name ".OUT","w",stdout); } solve(); cerr << '\n' << "Time collapsed: " << TIME << '\n'; return 0; } ```