Submission #1189988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189988		AlgorithmWarrior	Cities (BOI16_cities)	C++20	100 / 100	1482 ms	42940 KiB

cities

#include <bits/stdc++.h>

using namespace std;

long long const INF=1e18;
int const MAX=100005;
int n,k,m;
int cities[7];
struct edge{
    int nod,len;
};
vector<edge>G[MAX];
long long dist[MAX][35];

void read(){
    cin>>n>>k>>m;
    int i;
    for(i=1;i<=k;++i)
        cin>>cities[i];
    for(i=1;i<=m;++i){
        int a,b,c;
        cin>>a>>b>>c;
        G[a].push_back({b,c});
        G[b].push_back({a,c});
    }
}

struct path{
    int nod;
    long long dst;
};

class cmp{
public:
    bool operator()(path a,path b){
        return a.dst>b.dst;
    }
};

void dijkstra(int mask){
    int i;
    priority_queue<path,vector<path>,cmp>pq;
    for(i=1;i<=n;++i)
        pq.push({i,dist[i][mask]});
    while(!pq.empty()){
        auto [nd,dst]=pq.top();
        pq.pop();
        if(dst!=dist[nd][mask])
            continue;
        for(auto [vec,len] : G[nd])
            if(dist[vec][mask]>dst+len){
                dist[vec][mask]=dst+len;
                pq.push({vec,dist[vec][mask]});
            }
    }
}

void minself(long long& x,long long val){
    if(x>val)
        x=val;
}

void dijkstra_driver(){
    int i,mask;
    for(mask=1;mask<=k;++mask)
        for(i=1;i<=n;++i)
            if(cities[mask]==i)
                dist[i][1<<(mask-1)]=0;
            else
                dist[i][1<<(mask-1)]=INF;
    for(mask=1;mask<(1<<k);++mask){
        if(__builtin_popcount(mask)>1){
            for(i=1;i<=n;++i)
                dist[i][mask]=INF;
        }
        int submask=(mask-1)&mask;
        for(;submask;submask=(submask-1)&mask)
            for(i=1;i<=n;++i)
                minself(dist[i][mask],dist[i][submask]+dist[i][mask^submask]);
        dijkstra(mask);
    }
}

long long solve(){
    int i;
    long long ans=INF;
    for(i=1;i<=n;++i)
        minself(ans,dist[i][(1<<k)-1]);
    return ans;
}

int main()
{
    read();
    dijkstra_driver();
    cout<<solve();
    return 0;
}

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