Editorial for Bedao Grand Contest 05 - GFPROB
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Code mẫu
#include <bits/stdc++.h> using namespace std; const string filename = "GFPROB"; #define int long long typedef pair<int,int> ii; typedef pair<int,ii> iii; int n,m,k,s; int par[100001]; vector<ii> AdjList[100001]; int a[100001], d[100001], p[100001]; int anc(int x) { if (par[x] == x) return x; return par[x] = anc(par[x]); } void join(int x,int y) { par[anc(x)] = anc(y); } int res = 0; void cal_d() { priority_queue<ii, vector<ii>, greater<ii>> pq; for (int i=1;i<=n;i++) { par[i] = i; d[i] = 1e18; } for (int i=1;i<=k;i++) { int x = a[i]; d[x] = 0; p[x] = x; pq.push(ii(0,x)); } while(!pq.empty()) { int du = pq.top().first; int u = pq.top().second; pq.pop(); if (du != d[u]) continue; for (int i=0;i<AdjList[u].size();i++) { int v = AdjList[u][i].first; int w = AdjList[u][i].second; if (d[v] > du + w) { p[v] = p[u]; d[v] = du + w; pq.push(ii(d[v],v)); } } } } int32_t main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); freopen( (filename + ".inp").c_str(), "r", stdin); freopen( (filename + ".out").c_str(), "w", stdout); cin >> n >> m >> s >> k; for (int i=1;i<=k;i++) cin >> a[i]; while(m--) { int u,v,w; cin >> u >> v >> w; AdjList[u].push_back(ii(v,w)); AdjList[v].push_back(ii(u,w)); } cal_d(); vector<iii> c; for (int u=1;u<=n;u++) for (int i=0;i<AdjList[u].size();i++) { int v = AdjList[u][i].first; int w = AdjList[u][i].second; c.push_back(iii(d[u] + d[v] + w,ii(p[u],p[v]))); } sort(c.begin(),c.end()); int cnt = 0; for (int i=0;i<c.size();i++) { int w = c[i].first; int u = c[i].second.first; int v = c[i].second.second; if (anc(u) != anc(v)) { res += w; join(u,v); } if (cnt == k-1) break; } cout << res + d[s]; }
Comments