Submission #737548

#TimeUsernameProblemLanguageResultExecution timeMemory
737548Ronin13Relay Marathon (NOI20_relaymarathon)C++14
0 / 100
6030 ms139112 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); int bb = 500; vector <vector <pll> > g(nmax); 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); } vector <vector <pair<ll, int> > > G(n + 1); for(int s : sources){ priority_queue <pll> q; vector <ll> d(n + 1, 1e18); vector <bool> used(n + 1, false); q.push({0, s}); d[s] = 0; while(!q.empty()){ int v = q.top().s; q.pop(); if(used[v]) continue; used[v] = true; for(auto x : g[v]){ int to =x.f; ll len = x.s; if(d[to] > d[v] + len){ d[to] = d[v] + len; q.push({-d[to], to}); } } } vector <pll> vec; for(auto to : sources){ vec.epb(d[to], to); } sort(vec.begin(), vec.end()); for(int j = 0; j < 4; j++){ G[s].pb(vec[j]); } } vector <pair<ll, pii> > vec; for(int i = 1; i <= n; i++){ for(auto to : G[i]){ vec.pb({to.f, {to.s, i}}); } } 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() > 100) break; if(cnt[to.s.f] < 4 && cnt[to.s.s] < 4){ 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:80:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |     for(int i = 0; i < cand.size(); i++){
      |                    ~~^~~~~~~~~~~~~
RelayMarathon.cpp:81:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         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...