oj.uz

Submission #968891

# Submission time Handle Problem Language Result Execution time Memory
968891 2024-04-24T08:47:21 Z ttamx Cities (BOI16_cities) C++17
100 / 100
 1732 ms 48292 KB 
#include<bits/stdc++.h>
 
using namespace std;
 
using ll = long long;
using P = pair<ll,int>;
 
const int N=1e5+5;
const int K=35;
const ll INF=LLONG_MAX/2;
 
int n,m,k;
vector<pair<int,int>> adj[N];
ll dp[K][N];
 
int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k >> m;
    for(int mask=0;mask<1<<k;mask++)for(int i=1;i<=n;i++)dp[mask][i]=INF;
    for(int i=0;i<k;i++){
        int x;
        cin >> x;
        dp[1<<i][x]=0;
    }
    for(int i=0;i<m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v,w);
        adj[v].emplace_back(u,w);
    }
    for(int mask=1;mask<1<<k;mask++){
        for(int mask2=1;mask2<mask;mask2<<=1)if(mask&mask2)
            for(int i=1;i<=n;i++)dp[mask][i]=min(dp[mask][i],dp[mask2][i]+dp[mask^mask2][i]);
        priority_queue<P,vector<P>,greater<P>> pq;
        for(int i=1;i<=n;i++)if(dp[mask][i]!=INF)pq.emplace(dp[mask][i],i);
        while(!pq.empty()){
            auto [d,u]=pq.top();
            pq.pop();
            if(d>dp[mask][u])continue;
            for(auto [v,w]:adj[u])if(d+w<dp[mask][v]){
                dp[mask][v]=d+w;
                pq.emplace(d+w,v);
            }
        }
    }
    cout << *min_element(dp[(1<<k)-1]+1,dp[(1<<k)-1]+n+1);
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7260 KB Output is correct
2 Correct 2 ms 7448 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 2 ms 15452 KB Output is correct
5 Correct 4 ms 27964 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 373 ms 25036 KB Output is correct
2 Correct 349 ms 27548 KB Output is correct
3 Correct 215 ms 18648 KB Output is correct
4 Correct 55 ms 17668 KB Output is correct
5 Correct 186 ms 22536 KB Output is correct
6 Correct 41 ms 15440 KB Output is correct
7 Correct 4 ms 9564 KB Output is correct
8 Correct 3 ms 7604 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 15708 KB Output is correct
2 Correct 6 ms 15964 KB Output is correct
3 Correct 5 ms 15764 KB Output is correct
4 Correct 4 ms 15732 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 738 ms 33072 KB Output is correct
2 Correct 855 ms 35452 KB Output is correct
3 Correct 497 ms 26772 KB Output is correct
4 Correct 375 ms 29116 KB Output is correct
5 Correct 161 ms 24940 KB Output is correct
6 Correct 50 ms 25296 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1732 ms 47264 KB Output is correct
2 Correct 1661 ms 47556 KB Output is correct
3 Correct 1487 ms 48292 KB Output is correct
4 Correct 922 ms 39044 KB Output is correct
5 Correct 860 ms 42408 KB Output is correct
6 Correct 195 ms 37520 KB Output is correct
7 Correct 88 ms 37728 KB Output is correct