oj.uz

Submission #971951

# Submission time Handle Problem Language Result Execution time Memory
971951 2024-04-29T14:57:12 Z jadai007 Cities (BOI16_cities) C++17
100 / 100
 3236 ms 54216 KB 
#include<bits/stdc++.h>
#define int long long

using namespace std;

int dis[100100][40], u, v, w, n, m, k;
vector<pair<int, int>> vc[100100];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

int32_t main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n >> k >> m;
    for(int i = 1; i<=n; ++i) for(int j = 0; j<(1 << k); ++j) dis[i][j] = 1e18;
    for(int i = 0; i<k; ++i){
        int a; cin >> a;
        dis[a][(1 << i)] = 0;
    }
    for(int i = 1; i<=m; ++i){
        cin >> u >> v >> w;
        vc[u].emplace_back(v, w);
        vc[v].emplace_back(u, w);
    }
    for(int mask = 0; mask < (1 << k); ++mask){
        for(int i = 0; i<k; ++i){
            if(mask&(1 << i)){
                for(int j = 1; j<=n; ++j) dis[j][mask] = min(dis[j][mask], dis[j][mask^(1 << i)] + dis[j][(1 << i)]);
            }
        }
        for(int i = 1; i<=n; ++i) pq.emplace(dis[i][mask], i);
        while(!pq.empty()){
            int w = pq.top().first, u = pq.top().second;
            pq.pop();
            for(auto x:vc[u]){
                int v = x.first, ww = x.second;
                if(dis[v][mask] > dis[u][mask] + ww){
                    dis[v][mask] = dis[u][mask] + ww;
                    pq.emplace(dis[v][mask], v);
                }
            }
        }
    }
    int ans = 1e18;
    for(int i = 1; i<=n; ++i) ans = min(ans, dis[i][(1 << k) - 1]);
    cout << ans;
}

Compilation message

cities.cpp: In function 'int32_t main()':
cities.cpp:31:17: warning: unused variable 'w' [-Wunused-variable]
   31 |             int w = pq.top().first, u = pq.top().second;
      |                 ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4696 KB Output is correct
2 Correct 1 ms 4700 KB Output is correct
3 Correct 1 ms 4700 KB Output is correct
4 Correct 1 ms 4700 KB Output is correct
5 Correct 1 ms 4700 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 776 ms 53204 KB Output is correct
2 Correct 717 ms 53204 KB Output is correct
3 Correct 440 ms 43460 KB Output is correct
4 Correct 68 ms 17236 KB Output is correct
5 Correct 378 ms 53464 KB Output is correct
6 Correct 50 ms 17004 KB Output is correct
7 Correct 3 ms 4952 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct

Subtask #3
15.0 / 15.0

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

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1521 ms 53744 KB Output is correct
2 Correct 1369 ms 53432 KB Output is correct
3 Correct 951 ms 43464 KB Output is correct
4 Correct 741 ms 35868 KB Output is correct
5 Correct 153 ms 20620 KB Output is correct
6 Correct 68 ms 19280 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3079 ms 54216 KB Output is correct
2 Correct 3236 ms 53696 KB Output is correct
3 Correct 2881 ms 52152 KB Output is correct
4 Correct 1938 ms 43604 KB Output is correct
5 Correct 1399 ms 35780 KB Output is correct
6 Correct 254 ms 20660 KB Output is correct
7 Correct 89 ms 19536 KB Output is correct