oj.uz

Submission #968853

# Submission time Handle Problem Language Result Execution time Memory
968853 2024-04-24T07:39:59 Z ttamx Cities (BOI16_cities) C++17
100 / 100
 1585 ms 44056 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=mask-1;mask2;mask2=mask&(mask2-1))
            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 1 ms 7260 KB Output is correct
2 Correct 1 ms 7260 KB Output is correct
3 Correct 2 ms 9308 KB Output is correct
4 Correct 4 ms 15452 KB Output is correct
5 Correct 8 ms 27740 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 375 ms 22808 KB Output is correct
2 Correct 316 ms 23540 KB Output is correct
3 Correct 211 ms 16376 KB Output is correct
4 Correct 49 ms 14164 KB Output is correct
5 Correct 156 ms 18284 KB Output is correct
6 Correct 42 ms 12008 KB Output is correct
7 Correct 4 ms 9560 KB Output is correct
8 Correct 3 ms 7516 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 7 ms 15708 KB Output is correct
3 Correct 5 ms 15708 KB Output is correct
4 Correct 6 ms 15708 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 748 ms 31516 KB Output is correct
2 Correct 702 ms 31332 KB Output is correct
3 Correct 390 ms 24628 KB Output is correct
4 Correct 398 ms 25240 KB Output is correct
5 Correct 110 ms 21392 KB Output is correct
6 Correct 50 ms 21852 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1523 ms 43216 KB Output is correct
2 Correct 1585 ms 44056 KB Output is correct
3 Correct 1406 ms 43104 KB Output is correct
4 Correct 902 ms 36940 KB Output is correct
5 Correct 777 ms 37504 KB Output is correct
6 Correct 181 ms 33672 KB Output is correct
7 Correct 63 ms 34132 KB Output is correct