oj.uz

Submission #107390

# Submission time Handle Problem Language Result Execution time Memory
107390 2019-04-23T19:46:44 Z brcode Cities (BOI16_cities) C++14
14 / 100
 1942 ms 99412 KB 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const long long MAXN = 1e5+5;
vector<pair<long long,long long>> v1[MAXN];
long long dp[MAXN][100];
long long val[MAXN];
    long long n,m,k;
void fix(long long mask){
    for(long long i=1;i<=n;i++){
        //for each node, greedily remove the smallest bit and see whether selcting it + (mask-alteredmask)'s dp values are smaller than dp[i][mask]
        long long temp = mask;
        while(temp>0){
            if(dp[i][mask]>dp[i][temp] + dp[i][temp^mask]){
                dp[i][mask]=dp[i][temp] + dp[i][temp^mask];
            }
            temp = (temp-(long long)1) & mask;
        }
    }
    priority_queue<pair<long long,long long>> q1;
    for(long long i=1;i<=n;i++){
        q1.push(make_pair((long long)-1*dp[mask][i],i));
    }
    //rerun dijkstra's for this mask value
    while(!q1.empty()){
        auto hold = q1.top();
        q1.pop();
        long long curr = hold.second;
        long long dist = (long long)-1*hold.first;
        
        if(dp[curr][mask]!= dist){
            continue;
        }
        for(auto x:v1[curr]){
            if(dp[x.first][mask] > dp[curr][mask] + x.second){
                dp[x.first][mask] = dp[curr][mask] + x.second;
                q1.push(make_pair((long long)-1*dp[x.first][mask],x.first));
            }
        }
    }
}
void dijkstras(){
    for(long long i=0;i<k;i++){
        priority_queue<pair<long long,long long>> q1;
        q1.push(make_pair(0,val[i]));
        dp[val[i]][(1<<i)] = 0;
        while(!q1.empty()){
            auto hold = q1.top();
            q1.pop();
            long long curr = hold.second;
            
            long long dist = -1*hold.first;
            if(dp[curr][(1<<i)]!=dist){
                continue;
            }
            for(auto x:v1[curr]){
                long long to = x.first;
                
                if(dp[to][(1<<i)] >  dist+x.second){
                    dp[to][(1<<i)] = dist+x.second;
                    q1.push(make_pair(-1*dp[to][(1<<i)],to));
                }
            }
        }
    }
}
int main(){

    cin>>n>>k>>m;
    for(long long i=1;i<=n;i++){
        for(long long j=1;j<=(1<<k);j++){
            dp[i][j] = 1e18;
        }
    }
    for(long long i=0;i<k;i++){
        cin>>val[i];
    }
    for(long long i=0;i<m;i++){
        long long a,b,w;
        cin>>a>>b>>w;
        v1[a].push_back(make_pair(b,w));
        v1[b].push_back(make_pair(a,w));
        
    }
    //run a dijkstras from each of the compulsory nodes. dp[i][mask] denotes shortest distance to node i in a path consisting of the nodes in mask (dijkstra's calculates only for a single compulsory node)
    dijkstras();
    for(long long i=3;i<(1<<k);i++){
        //cout<<i<<endl;
        //calculate the rest
        fix(i);
    }
    long long ans = 1e18;
    for(long long i=1;i<=n;i++){
        ans = min(ans,dp[i][(1<<k)-1]);
    }
    cout<<ans<<endl;
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 5 ms 2688 KB Output is correct
4 Incorrect 5 ms 2688 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 864 ms 99324 KB Output is correct
2 Correct 799 ms 98488 KB Output is correct
3 Correct 507 ms 92016 KB Output is correct
4 Correct 226 ms 16084 KB Output is correct
5 Correct 591 ms 98908 KB Output is correct
6 Correct 229 ms 15852 KB Output is correct
7 Correct 8 ms 3712 KB Output is correct
8 Correct 8 ms 3632 KB Output is correct

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 3584 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 1167 ms 99192 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 1942 ms 99412 KB Output isn't correct
2 Halted 0 ms 0 KB -