Submission #890098

#TimeUsernameProblemLanguageResultExecution timeMemory
890098vjudge1Relay Marathon (NOI20_relaymarathon)C++14
17 / 100
6070 ms13652 KiB
#include<bits/stdc++.h> using namespace std; #define int long long #define all(a) (a).begin(), (a).end() const int N=1e5+1, MAX_SIZE=6; int n, m, k; vector<pair<int, int>> dist[N]; vector<pair<int, int>> g[N]; bool optimize(int idx, pair<int, int> val){ for (auto &i:dist[idx]) if (i.second==val.second){ if (i.first>val.first){ i=val; return 1; } return 0; } if ((int)dist[idx].size()<MAX_SIZE){ dist[idx].push_back(val); sort(dist[idx].begin(), dist[idx].end()); return 1; } if (val.first<dist[idx].back().first){ dist[idx].push_back(val); sort(dist[idx].begin(), dist[idx].end()); dist[idx].pop_back(); return 1; } return 0; } bool optimize(int idx, int par, int w){ bool ans=0; for (auto &i:dist[par]){ ans|=optimize(idx, {i.first+w, i.second}); } return ans; } struct cmp{ bool operator()(const pair<vector<pair<int, int>>, int> &a, const pair<vector<pair<int, int>>, int> &b){ for (int i=0; i<min<int>(a.first.size(), b.first.size()); ++i) if (a.first[i]!=b.first[i]) return a.first[i]<b.first[i]; if (a.first.size()!=b.first.size()) return a.first.size()<b.first.size(); return a.second<b.second; } }; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> m >> k; for (int i=1; i<=m; ++i){ int u, v, w; cin >> u >> v >> w; g[u].emplace_back(v, w); g[v].emplace_back(u, w); } priority_queue<pair<vector<pair<int, int>>, int>, vector<pair<vector<pair<int, int>>, int>>, cmp> pq; for (int i=1; i<=k; ++i){ int x; cin >> x; dist[x].emplace_back(0, x); pq.emplace(dist[x], x); } while (pq.size()){ auto tt=pq.top().first; int u=pq.top().second; pq.pop(); if (dist[u]!=tt) continue; for (auto &e:g[u]){ int v=e.first, w=e.second; if (optimize(v, u, w)) pq.emplace(dist[v], v); } } int ans=1e18; set<pair<int, pair<int, int>>> st; for (int i=1; i<=n; ++i){ vector<pair<int, int>> d2; for (auto &j:dist[i]){ int u=i, v=j.second, d=j.first; if (d && find(all(dist[v]), pair<int, int>{d, u})!=dist[v].end()){ st.insert({d, {u, v}}); st.insert({d, {v, u}}); d2.emplace_back(d, v); } } dist[i].swap(d2); } for (int i=1; i<=n; ++i){ int u=i; for (auto &j:dist[i]){ int v=j.second; for (auto &t:dist[u]){ st.erase({t.first, {u, t.second}}); st.erase({t.first, {t.second, u}}); } for (auto &t:dist[v]){ st.erase({t.first, {v, t.second}}); st.erase({t.first, {t.second, v}}); } if (st.size()){ ans=min(ans, j.first+st.begin()->first); } for (auto &t:dist[u]){ st.insert({t.first, {u, t.second}}); st.insert({t.first, {t.second, u}}); } for (auto &t:dist[v]){ st.insert({t.first, {v, t.second}}); st.insert({t.first, {t.second, v}}); } } } cout << ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...