Submission #737550

#	Time	Username	Problem	Language	Result	Execution time	Memory
737550		Ronin13	Relay Marathon (NOI20_relaymarathon)	C++14	17 / 100	6040 ms	138944 KiB

RelayMarathon

#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 = 50;
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 < min(k, bb); 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() > 1000) break;
        if(cnt[to.s.f] < bb && cnt[to.s.s] < bb){
            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++){
      |                       ~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 12 / 12
• Subtask 3: 0 / 25
• Subtask 4: 0 / 58