Submission #961875

#	Time	Username	Problem	Language	Result	Execution time	Memory
961875		shezitt	Cities (BOI16_cities)	C++14	0 / 100	1 ms	604 KiB

cities

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

using ll = long long;

#define int ll
#define pb push_back
#define endl '\n'
#define fore(i, a, b) for(int i=a; i<b; ++i)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define ii pair<int,int>

const int N = 21;

int n, k, m;
vector<ii> adj[N];
vector<int> important;

struct edge {
    int u, v, c;
    bool operator<(const edge &otro){
        return c < otro.c;
    }
};

signed main(){  
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> k >> m;
    important.resize(k);
    fore(i, 0, k){
        cin >> important[i];
        important[i]--;
    }

    vector<edge> edlist;

    fore(i, 0, m){
        int u, v, c;
        cin >> u >> v >> c;
        u--, v--;
        adj[u].pb(make_pair(v, c));
        adj[v].pb(make_pair(u, c));
        edlist.pb({u, v, c});
        edlist.pb({v, u, c});
    }

    int ans = 4e18;

    for(int mask=0; mask<(1<<n); ++mask){

        bool sirve = 1;
        for(int x : important){
            if(((1<<x)&mask) == 0){
                sirve = 0;
                break;
            }
        }   
        if(sirve == 0) continue;

        vector<edge> curlist;

        for(auto [u, v, c] : edlist){
            if(((1 << u) & mask) == 0 or ((1 << v) & mask) == 0){
                continue;
            }
            curlist.pb({u, v, c});
        }

        sort(all(curlist));

        vector<bool> vis(n);

        int cur = 0;
        for(auto [u, v, c] : curlist){
            if(vis[u] && vis[v]) continue;
            cur += c;
            vis[u] = vis[v] = 1;
        }

        bool ok = 1;
        for(int x : important){
            ok &= vis[x];
        }
        if(ok){
            ans = min(ans, cur);
        }

    }

    cout << ans;

}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:69:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   69 |         for(auto [u, v, c] : edlist){
      |                  ^
cities.cpp:81:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   81 |         for(auto [u, v, c] : curlist){
      |                  ^

• Subtask 1: 0 / 22
• Subtask 2: 0 / 14
• Subtask 3: 0 / 15
• Subtask 4: 0 / 23
• Subtask 5: 0 / 26