Submission #559939

#	Time	Username	Problem	Language	Result	Execution time	Memory
559939		abcvuitunggio	Cities (BOI16_cities)	C++17	100 / 100	3378 ms	45648 KiB

cities

#include <iostream>
#include <queue>
#include <vector>
#define int long long
using namespace std;
const int mx=1000000000000000001;
int l[100001],dp[100001][32],n,m,k,a[100001],u,v,w,res=mx;
vector <pair <int, int> > ke[100001];
void dijkstra(){
    priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > > q;
    for (int i=1;i<=n;i++)
        q.push({l[i],i});
    while (!q.empty()){
        int u=q.top().second,lu=q.top().first;
        q.pop();
        if (l[u]!=lu)
            continue;
        for (auto v:ke[u])
            if (l[v.first]>l[u]+v.second){
                l[v.first]=l[u]+v.second;
                q.push({l[v.first],v.first});
            }
    }
}
signed main(){
    ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
    cin >> n >> k >> m;
    for (int i=1;i<=n;i++){
        l[i]=mx;
        for (int j=0;j<(1<<k);j++)
            dp[i][j]=mx;
    }
    for (int i=0;i<k;i++){
        cin >> a[i];
        dp[a[i]][1<<i]=0;
    }
    for (int i=0;i<m;i++){
        cin >> u >> v >> w;
        ke[u].push_back({v,w});
        ke[v].push_back({u,w});
    }
    for (int mask=0;mask<(1<<k);mask++){
        for (int i=0;i<(1<<k);i++)
            for (int j=0;j<(1<<k);j++)
                if ((i|j)==mask)
                    for (int l=1;l<=n;l++)
                        dp[l][mask]=min(dp[l][mask],dp[l][i]+dp[l][j]);
        for (int i=1;i<=n;i++)
            l[i]=dp[i][mask];
        dijkstra();
        for (int i=1;i<=n;i++)
            dp[i][mask]=l[i];
    }
    for (int i=1;i<=n;i++)
        res=min(res,dp[i][(1<<k)-1]);
    cout << res;
}

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