제출 #107391

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
107391		brcode	Cities (BOI16_cities)	C++14	100 / 100	5025 ms	102352 KiB

cities

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long MAXN = 1e5+5;
vector<pair<long long,long long>> v1[MAXN];
long long dp[MAXN][100];
long long val[MAXN];
    long long n,m,k;
void fix(long long mask){
    for(long long i=1;i<=n;i++){
        //for each node, greedily remove the smallest bit and see whether selcting it + (mask-alteredmask)'s dp values are smaller than dp[i][mask]
        long long temp = mask;
        while(temp>0){
            if(dp[i][mask]>dp[i][temp] + dp[i][temp^mask]){
                dp[i][mask]=dp[i][temp] + dp[i][temp^mask];
            }
            temp = (temp-(long long)1) & mask;
        }
    }
    priority_queue<pair<long long,long long>> q1;
    for(long long i=1;i<=n;i++){
        q1.push(make_pair((long long)-1*dp[i][mask],i));
    }
    //rerun dijkstra's for this mask value
    while(!q1.empty()){
        auto hold = q1.top();
        q1.pop();
        long long curr = hold.second;
        long long dist = (long long)-1*hold.first;
        
        if(dp[curr][mask]!= dist){
            continue;
        }
        for(auto x:v1[curr]){
            if(dp[x.first][mask] > dp[curr][mask] + x.second){
                dp[x.first][mask] = dp[curr][mask] + x.second;
                q1.push(make_pair((long long)-1*dp[x.first][mask],x.first));
            }
        }
    }
}
void dijkstras(){
    for(long long i=0;i<k;i++){
        priority_queue<pair<long long,long long>> q1;
        q1.push(make_pair(0,val[i]));
        dp[val[i]][(1<<i)] = 0;
        while(!q1.empty()){
            auto hold = q1.top();
            q1.pop();
            long long curr = hold.second;
            
            long long dist = -1*hold.first;
            if(dp[curr][(1<<i)]!=dist){
                continue;
            }
            for(auto x:v1[curr]){
                long long to = x.first;
                
                if(dp[to][(1<<i)] >  dist+x.second){
                    dp[to][(1<<i)] = dist+x.second;
                    q1.push(make_pair(-1*dp[to][(1<<i)],to));
                }
            }
        }
    }
}
int main(){

    cin>>n>>k>>m;
    for(long long i=1;i<=n;i++){
        for(long long j=1;j<=(1<<k);j++){
            dp[i][j] = 1e18;
        }
    }
    for(long long i=0;i<k;i++){
        cin>>val[i];
    }
    for(long long i=0;i<m;i++){
        long long a,b,w;
        cin>>a>>b>>w;
        v1[a].push_back(make_pair(b,w));
        v1[b].push_back(make_pair(a,w));
        
    }
    //run a dijkstras from each of the compulsory nodes. dp[i][mask] denotes shortest distance to node i in a path consisting of the nodes in mask (dijkstra's calculates only for a single compulsory node)
    dijkstras();
    for(long long i=3;i<(1<<k);i++){
        //cout<<i<<endl;
        //calculate the rest
        fix(i);
    }
    long long ans = 1e18;
    for(long long i=1;i<=n;i++){
        ans = min(ans,dp[i][(1<<k)-1]);
    }
    cout<<ans<<endl;
}

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