Submission #1282625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282625		Ludissey	Cities (BOI16_cities)	C++20	100 / 100	3673 ms	156596 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<vector<int>> sm_dist(k,vector<int>(n));
    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});
    }
    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});
                }
            }
        }
        for (int j = 0; j < n; j++)
        {
            sm_dist[i][j]=dist[j];
        }
        
    }
    int mn=1e18;
    vector<vector<int>> dist(n,vector<int>(1<<k,1e18));
    vector<vector<bool>> visited(n,vector<bool>(1<<k,0));
    priority_queue<pair<int,pair<int,int>>> pq;
    for (int i = 0; i < n; i++)
    {
        dist[i][0]=0;
        pq.push({-dist[i][0],{i,0}});
    }
    while(!pq.empty()){
        int x=pq.top().second.first,mask=pq.top().second.second; pq.pop();
        if(visited[x][mask]) continue;
        visited[x][mask]=true;
        if(mask==(1<<k)-1) mn=min(dist[x][mask],mn);
        for (auto u : neigh[x])
        {
            if(dist[x][mask]+u.first.second<dist[u.first.first][mask]){
                dist[u.first.first][mask]=dist[x][mask]+u.first.second;
                pq.push({-dist[u.first.first][mask],{u.first.first,mask}});
            }
        }
        for (int i = 0; i < k; i++)
        {
            if(!(mask&(1<<i))&&dist[x][mask]+sm_dist[i][x]<dist[x][mask^(1<<i)]) {
                dist[x][mask^(1<<i)]=dist[x][mask]+sm_dist[i][x];
                pq.push({-dist[x][mask^(1<<i)], {x,mask^(1<<i)}});
            }
        }
        
    }
    cout << mn << "\n";
    return 0;   
}

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