Submission #737552

#TimeUsernameProblemLanguageResultExecution timeMemory
737552Ronin13Relay Marathon (NOI20_relaymarathon)C++14
17 / 100
6062 ms310620 KiB
#include <bits/stdc++.h> #define ll long long #define ull unsigned ll #define f first #define s second #define pii pair<int,int> #define pll pair<ll,ll> #define pb push_back #define epb emplace_back using namespace std; const int nmax = 300001; vector <ll> bit(nmax); vector <vector <pll> > dp(nmax); map <pii, bool> used; vector <vector <pll> > g(nmax); priority_queue <pair<ll, pii> > q; void upd(int u, int x, ll len){ bool tt; tt = false; for(int j = 0; j < 25; j++){ if(dp[u][j].s == x){ tt = true; if(len > dp[u][j].f) continue; dp[u][j].f = len; q.push({-dp[u][j].f, {u, dp[u][j].s}}); } } if(!tt){ if(len < dp[u].back().f) dp[u].pb({len, x}), q.push({-len, {u, x}}); } sort(dp[u].begin(), dp[u].end()); if(dp[u].size() > 25) dp[u].pop_back(); } int main(){ int n, k, m; cin >> n >> m >> k; for(int i = 1; i <= m; i++){ int u, v; cin >> u >> v; ll w; cin >> w; g[u].pb({v, w}); g[v].pb({u, w}); } vector <int> sources; for(int i = 1 ;i <= k; i++){ int x; cin >> x; sources.pb(x); } // cout << 1; for(int i = 1; i <= n; i++){ for(int j = 0; j < 25; j++) dp[i].pb({1e18, 0}); } // cout << 1; for(int to : sources){ dp[to][0] = {0, to}; q.push({0, {to, to}}); } //cout << 1; while(!q.empty()){ int v = q.top().s.f, y = q.top().s.s; ll val = -q.top().f; q.pop(); if(used[{v, y}]) continue; used[{v, y}] = true; for(auto ed : g[v]){ int to = ed.f; ll len = ed.s + val; upd(to, y, len); } } vector <pair<ll, pii> > vec; for(int to : sources){ for(int j = 0; j < 25; j++){ if(dp[to][j].f != 1e18) vec.pb({dp[to][j].f, {to, dp[to][j].s}}); } } sort(vec.begin(), vec.end()); int cnt[n + 1]; fill(cnt, cnt + n + 1, 0); vector <pair<ll, pii> > cand; for(auto to : vec){ if(cand.size() > 500) break; if(cnt[to.s.f] < 25 && cnt[to.s.s] < 25){ cand.pb(to); cnt[to.s.f]++; cnt[to.s.s]++; } } // cout << 1; ll ans = 1e18; for(int i = 0; i < cand.size(); i++){ for(int j =0; j < cand.size(); j++){ set <int> st; st.insert(cand[i].s.f); st.insert(cand[i].s.s); st.insert(cand[j].s.f); st.insert(cand[j].s.s); if(st.size() == 4){ ans = min(ans, cand[i].f + cand[j].f); } } } cout << ans; return 0; }

Compilation message (stderr)

RelayMarathon.cpp: In function 'int main()':
RelayMarathon.cpp:97:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> >, std::allocator<std::pair<long long int, std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for(int i = 0; i < cand.size(); i++){
      |                    ~~^~~~~~~~~~~~~
RelayMarathon.cpp:98:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> >, std::allocator<std::pair<long long int, std::pair<int, int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   98 |         for(int j =0; j < cand.size(); j++){
      |                       ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...