Submission #755692

#	Time	Username	Problem	Language	Result	Execution time	Memory
755692		Ahmed57	Cities (BOI16_cities)	C++17	100 / 100	3801 ms	52572 KiB

cities

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
long long lol[5][200001];
vector<int> imp;int n,k,m;
vector<pair<int,int>> adj[200001];
void d(int st){
    priority_queue<pair<long long,long long>> q1;
    q1.push({0,imp[st]});
    lol[st][imp[st]] = 0;
    while(!q1.empty()){
        long long co = q1.top().first*-1;
        long long no = q1.top().second;
        q1.pop();
        if (co>lol[st][no]) continue ;
        for(auto i:adj[no]){
            if(lol[st][i.first]>(i.second+co)){
                lol[st][i.first] = (i.second+co);
                q1.push({lol[st][i.first]*-1,i.first});
            }
        }
    }
}
long long calc(){
    long long cost[n+1][(1<<k)];
    memset(cost,0,sizeof cost);
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<(1<<k);j++){
            cost[i][j] = 1e18;
        }
    }
    for(int i = 1;i<=n;i++){
        cost[i][0] = 0;
    }
    for(int le = 0;le<(1<<k)-1;le++){
    priority_queue<pair<long long,int>> q1;
    for(int i = 1;i<=n;i++){
        q1.push({(-1)*cost[i][le],i});
    }
    while(!q1.empty()){
        long long co = q1.top().first*-1;
        int no = q1.top().second;
        q1.pop();
        if (co>cost[no][le]) continue ;
        for(int submask = 0;submask<(1<<k);submask++){
            if((le&submask)!=0)continue;
            int nemask = (submask|le);
            long long necost = co;
            for(int j = 0;j<k;j++){
                if(submask&(1<<j)){
                    necost+=lol[j][no];
                }
            }
            for(auto i:adj[no]){
                if(cost[i.first][nemask]>(necost+i.second)){
                cost[i.first][nemask]=(necost+i.second);
                if(submask==0)q1.push({cost[i.first][nemask]*-1,i.first});
                }
            }
        }
    }
    }
    long long ans = 1e18;
    for(int i = 1;i<=n;i++){
        ans = min(ans,cost[i][(1<<k)-1]);
    }
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>k>>m;
    for(int i = 1;i<=n;i++){
        adj[i].push_back({i,0});
    }
    for(int i= 0;i<k;i++){
        int x;cin>>x;
        imp.push_back(x);
    }
    for(int i = 0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    for(int i = 0;i<k;i++){
        for(int j = 1;j<=n;j++)lol[i][j] = 1e18;
        d(i);
    }
    cout<<calc()<<endl;
}

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