oj.uz

Submission #485523

# Submission time Handle Problem Language Result Execution time Memory
485523 2021-11-08T03:44:12 Z phamhoanghiep Cities (BOI16_cities) C++14
100 / 100
 2451 ms 44828 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int,int> ii;
const int maxn=1e5+5;
const int inf=1e15;
int dp[1<<5][maxn];
vector<ii> AdjList[maxn];
int sp[maxn];
int rsp[maxn];
int n,m,k;
void dijkstra(int mask) {
    //cout<<"dijk "<<mask<<endl;
    priority_queue<ii,vector<ii>,greater<ii>> pq;
    for(int i=1 ; i<=n ; i++) {
        pq.push(ii(dp[mask][i],i));
        //cout<<"dp "<<mask<<" "<<i<<" = "<<dp[mask][i]<<endl;
    }
    while(!pq.empty()) {
        ii tmp=pq.top();
        pq.pop();
        int val=tmp.first;
        int node=tmp.second;
        //cout<<"val node "<<val<<" "<<node<<endl;
        if(dp[mask][node]>val) continue;
        //cout<<"dp "<<mask<<" "<<node<<" = "<<dp[mask][node]<<endl;
        //cout<<"val node "<<val<<" "<<node<<endl;
        for(ii tmp: AdjList[node]) {
            int u=tmp.first;
            int w=tmp.second;
            if(dp[mask][u]>dp[mask][node]+w) {
                dp[mask][u]=dp[mask][node]+w;
                pq.push(ii(dp[mask][u],u));
            }
        }
    }
}
signed main() {
    cin>>n>>k>>m;
    for(int i=0 ; i<k ; i++) {
        cin>>sp[i];
        rsp[sp[i]]=i+1;
    }
    for(int i=1 ; i<=m ; i++) {
        int u,v,w;
        cin>>u>>v>>w;
        AdjList[u].push_back(ii(v,w));
        AdjList[v].push_back(ii(u,w));
    }
    for(int i=0 ; i<(1<<k) ; i++) {
        for(int j=1 ; j<=n ; j++) {
            dp[i][j]=inf;
        }
    }
    for(int i=0 ; i<k ; i++) {
        dp[(1<<i)][sp[i]]=0;
        //cout<<"dp "<<(1<<i)<<" "<<sp[i]<<endl;
    }
    for(int i=1 ; i<=n ; i++) dp[0][i]=0;
    for(int mask=0 ; mask<(1<<k) ; mask++) {
        for(int i=1 ; i<=n ; i++) {
            //cout<<dp[mask][i]<<" ";
        }
        //cout<<endl;
    }
    for(int mask=1 ; mask<(1<<k) ; mask++) {
        //cout<<"mask = "<<mask<<endl;
        for(int mask2=mask ; mask2>0 ; mask2=(mask2-1)&mask) {
            int rmask=mask^mask2;
            //cout<<"mask2 rmask "<<mask2<<" "<<rmask<<endl;
            for(int i=1 ; i<=n ; i++) {
                if(!rsp[i]) dp[mask][i]=min(dp[mask][i],dp[mask2][i]+dp[rmask][i]);
                else dp[mask][i]=min(dp[mask][i],dp[mask2][i]+dp[rmask^(1<<(rsp[i]-1))][i]);
            }
        }
        dijkstra(mask);
    }
    int ans=inf;
    int full=(1<<k)-1;
    for(int i=1 ; i<=n ; i++) ans=min(ans,dp[full][i]);
    cout<<ans;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2636 KB Output is correct
5 Correct 1 ms 2764 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 707 ms 25748 KB Output is correct
2 Correct 677 ms 25288 KB Output is correct
3 Correct 412 ms 17796 KB Output is correct
4 Correct 167 ms 11812 KB Output is correct
5 Correct 428 ms 22640 KB Output is correct
6 Correct 158 ms 11716 KB Output is correct
7 Correct 4 ms 2892 KB Output is correct
8 Correct 4 ms 2764 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3020 KB Output is correct
2 Correct 7 ms 3020 KB Output is correct
3 Correct 6 ms 2892 KB Output is correct
4 Correct 5 ms 2976 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1281 ms 32364 KB Output is correct
2 Correct 1192 ms 31560 KB Output is correct
3 Correct 753 ms 24064 KB Output is correct
4 Correct 762 ms 23312 KB Output is correct
5 Correct 270 ms 14468 KB Output is correct
6 Correct 176 ms 14164 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2451 ms 44828 KB Output is correct
2 Correct 2440 ms 44560 KB Output is correct
3 Correct 2244 ms 44204 KB Output is correct
4 Correct 1479 ms 36592 KB Output is correct
5 Correct 1325 ms 29488 KB Output is correct
6 Correct 374 ms 15944 KB Output is correct
7 Correct 208 ms 14320 KB Output is correct