oj.uz

Submission #107391

# Submission time Handle Problem Language Result Execution time Memory
107391 2019-04-23T19:49:06 Z brcode Cities (BOI16_cities) C++14
100 / 100
 5025 ms 102352 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[i][mask],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
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 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 Correct 5 ms 2688 KB Output is correct
5 Correct 6 ms 2688 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1278 ms 97992 KB Output is correct
2 Correct 1238 ms 97236 KB Output is correct
3 Correct 770 ms 89928 KB Output is correct
4 Correct 229 ms 12516 KB Output is correct
5 Correct 742 ms 95692 KB Output is correct
6 Correct 261 ms 12464 KB Output is correct
7 Correct 25 ms 3584 KB Output is correct
8 Correct 7 ms 3712 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3584 KB Output is correct
2 Correct 12 ms 3584 KB Output is correct
3 Correct 12 ms 3584 KB Output is correct
4 Correct 9 ms 3200 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2417 ms 97932 KB Output is correct
2 Correct 2406 ms 101672 KB Output is correct
3 Correct 1734 ms 92176 KB Output is correct
4 Correct 1464 ms 60096 KB Output is correct
5 Correct 455 ms 24212 KB Output is correct
6 Correct 246 ms 17912 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4891 ms 98128 KB Output is correct
2 Correct 5025 ms 102352 KB Output is correct
3 Correct 4770 ms 101632 KB Output is correct
4 Correct 3465 ms 92232 KB Output is correct
5 Correct 2498 ms 60136 KB Output is correct
6 Correct 658 ms 24388 KB Output is correct
7 Correct 264 ms 17784 KB Output is correct