Submission #1281678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281678		Ludissey	Cities (BOI16_cities)	C++20	0 / 100	257 ms	23896 KiB

cities

#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define int long long
using namespace std;

const int LOG=24;

signed main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    int n,k,m; cin >> n >> k >> m;
    vector<vector<pair<pair<int,int>,int>>> neigh(n);
    vector<int> spec(k);
    vector<int> val(m);
    vector<vector<vector<int>>> route(k,vector<vector<int>>(k));
    for (int i = 0; i < k; i++) cin >> spec[i],spec[i]--; 
    
    for (int i = 0; i < m; i++)
    {
        int a,b,c; cin >> a >> b >> c;
        neigh[a-1].push_back({{b-1,c},i});
        neigh[b-1].push_back({{a-1,c},i});
        val[i]=c;
    }
    for (int i = 0; i < sz(spec); i++)
    {
        vector<int> dist(n,1e18);
        vector<pair<int,int>> prev(n);
        vector<int> visited(n);
        priority_queue<pair<int,int>> pq;
        dist[spec[i]]=0;
        pq.push({-dist[spec[i]],spec[i]});
        while(!pq.empty()){
            int x=pq.top().second; pq.pop();
            if(visited[x]) continue;
            visited[x]=true;
            for (auto u : neigh[x])
            {
                if(dist[x]+u.first.second<dist[u.first.first]){
                    dist[u.first.first]=dist[x]+u.first.second;
                    pq.push({-dist[u.first.first],u.first.first});
                    prev[u.first.first]={x,u.second};
                }
            }
        }
        for (int j = i+1; j < sz(spec); j++)
        {
            int u=spec[j];
            while(u!=spec[i]){
                route[i][j].push_back(prev[u].second);
                u=prev[u].first;
            }
        }
    }
    int mn=1e18;
    for (int mask = 0; mask < (1<<((k*(k-1))/2)); mask++)
    {
        int c=0;
        int sm=0;
        vector<bool> cn(m,false);
        vector<bool> vst(k,0);
        bool ps=false;
        vst[0]=true;
        for (int i = 0; i < sz(spec); i++)
        {
            if(vst[i]==false){
                ps=true;
                break;
            }
            for (int j = i+1; j < sz(spec); j++)
            {
                if(mask&(1<<c)){
                    vst[j]=true;
                }
                c++;
            }
        }
        if(ps) continue;
        c=0;
        for (int i = 0; i < sz(spec); i++)
        {
            for (int j = i+1; j < sz(spec); j++)
            {
                if(mask&(1<<c)){
                    for (auto u : route[i][j]) cn[u]=true;
                }
                c++;
            }
        }
        for (int i = 0; i < m; i++)
        {
            sm+=val[i]*cn[i];
        }
        mn=min(sm,mn);
    }
    cout << mn << "\n";
    return 0;   
}

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