oj.uz

Submission #755692

# Submission time Handle Problem Language Result Execution time Memory
755692 2023-06-10T15:02:01 Z Ahmed57 Cities (BOI16_cities) C++17
100 / 100
 3801 ms 52572 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>

using namespace std;
long long lol[5][200001];
vector<int> imp;int n,k,m;
vector<pair<int,int>> adj[200001];
void d(int st){
    priority_queue<pair<long long,long long>> q1;
    q1.push({0,imp[st]});
    lol[st][imp[st]] = 0;
    while(!q1.empty()){
        long long co = q1.top().first*-1;
        long long no = q1.top().second;
        q1.pop();
        if (co>lol[st][no]) continue ;
        for(auto i:adj[no]){
            if(lol[st][i.first]>(i.second+co)){
                lol[st][i.first] = (i.second+co);
                q1.push({lol[st][i.first]*-1,i.first});
            }
        }
    }
}
long long calc(){
    long long cost[n+1][(1<<k)];
    memset(cost,0,sizeof cost);
    for(int i = 1;i<=n;i++){
        for(int j = 0;j<(1<<k);j++){
            cost[i][j] = 1e18;
        }
    }
    for(int i = 1;i<=n;i++){
        cost[i][0] = 0;
    }
    for(int le = 0;le<(1<<k)-1;le++){
    priority_queue<pair<long long,int>> q1;
    for(int i = 1;i<=n;i++){
        q1.push({(-1)*cost[i][le],i});
    }
    while(!q1.empty()){
        long long co = q1.top().first*-1;
        int no = q1.top().second;
        q1.pop();
        if (co>cost[no][le]) continue ;
        for(int submask = 0;submask<(1<<k);submask++){
            if((le&submask)!=0)continue;
            int nemask = (submask|le);
            long long necost = co;
            for(int j = 0;j<k;j++){
                if(submask&(1<<j)){
                    necost+=lol[j][no];
                }
            }
            for(auto i:adj[no]){
                if(cost[i.first][nemask]>(necost+i.second)){
                cost[i.first][nemask]=(necost+i.second);
                if(submask==0)q1.push({cost[i.first][nemask]*-1,i.first});
                }
            }
        }
    }
    }
    long long ans = 1e18;
    for(int i = 1;i<=n;i++){
        ans = min(ans,cost[i][(1<<k)-1]);
    }
    return ans;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>k>>m;
    for(int i = 1;i<=n;i++){
        adj[i].push_back({i,0});
    }
    for(int i= 0;i<k;i++){
        int x;cin>>x;
        imp.push_back(x);
    }
    for(int i = 0;i<m;i++){
        int a,b,c;cin>>a>>b>>c;
        adj[a].push_back({b,c});
        adj[b].push_back({a,c});
    }
    for(int i = 0;i<k;i++){
        for(int j = 1;j<=n;j++)lol[i][j] = 1e18;
        d(i);
    }
    cout<<calc()<<endl;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 3 ms 5032 KB Output is correct
5 Correct 3 ms 5028 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 726 ms 32176 KB Output is correct
2 Correct 669 ms 29204 KB Output is correct
3 Correct 467 ms 25044 KB Output is correct
4 Correct 75 ms 13236 KB Output is correct
5 Correct 336 ms 25512 KB Output is correct
6 Correct 62 ms 13196 KB Output is correct
7 Correct 6 ms 5200 KB Output is correct
8 Correct 5 ms 5204 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 5332 KB Output is correct
2 Correct 8 ms 5444 KB Output is correct
3 Correct 7 ms 5204 KB Output is correct
4 Correct 7 ms 5168 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1601 ms 39088 KB Output is correct
2 Correct 1532 ms 38524 KB Output is correct
3 Correct 1175 ms 32156 KB Output is correct
4 Correct 898 ms 26956 KB Output is correct
5 Correct 209 ms 15900 KB Output is correct
6 Correct 103 ms 15052 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3602 ms 52424 KB Output is correct
2 Correct 3801 ms 52572 KB Output is correct
3 Correct 3460 ms 51788 KB Output is correct
4 Correct 2568 ms 45616 KB Output is correct
5 Correct 1985 ms 33692 KB Output is correct
6 Correct 421 ms 17340 KB Output is correct
7 Correct 186 ms 15040 KB Output is correct