Submission #1138712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138712		mnbvcxz123	Cities (BOI16_cities)	C++20	100 / 100	4118 ms	144372 KiB

cities

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using pi=pair<ll,ll>;

#define ar array

constexpr int MAXN=1e5+5;
constexpr ll inf=1e18;

ll dist[5][MAXN];
ll dp[1<<5][MAXN];
ll imp[5];
bool vis[MAXN];
bool vis2[1<<5][MAXN];
int n,k,m;
vector<pi>g[MAXN];

void dij(int s, ll dist[]){
    priority_queue<pi,vector<pi>,greater<pi>>q;
    fill(dist,dist+n+1,inf);
    memset(vis,0,sizeof vis);
    dist[s]=0;
    q.push({0,s});
    while(!q.empty()){
        auto [d,u]=q.top();
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(const auto&[v,w]:g[u])
            if(dist[v]>dist[u]+w){
                dist[v]=dist[u]+w;
                q.push({dist[v],v});
            }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin>>n>>k>>m;
    for(int i=0;i<k;++i)cin>>imp[i];
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        g[a].push_back({b,c});
        g[b].push_back({a,c});
    }
    for(int i=0;i<k;++i)
        dij(imp[i],dist[i]);
    priority_queue<ar<ll,3>,vector<ar<ll,3>>,greater<ar<ll,3>>>q;
    for(int i=1;i<=n;++i)
        for(int j=0;j<(1<<k);++j)
            dp[j][i]=inf;
    for(int i=0;i<k;++i){
        dp[1<<i][imp[i]]=0;
        q.push({0,imp[i],1<<i});
    }
    while(!q.empty()){
        auto [d,u,s]=q.top();
        q.pop();
        if(vis2[s][u])continue;
        vis2[s][u]=1;
        for(const auto&[v,w]:g[u])
            if(!vis2[s][v] and dp[s][v]>d+w){
                dp[s][v]=d+w;
                q.push({dp[s][v],v,s});
            }
        for(int i=0;i<k;++i){
            int nw=s|(1<<i);
            if(!vis2[nw][u] and dp[nw][u]>d+dist[i][u]){
                dp[nw][u]=d+dist[i][u];
                q.push({dp[nw][u],u,nw});
            }
        }
    }
    ll ret=inf;
    for(int i=1;i<=n;++i)
        ret=min(ret,dp[(1<<k)-1][i]);
    cout<<ret<<'\n';
}

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