oj.uz

Submission #969156

# Submission time Handle Problem Language Result Execution time Memory
969156 2024-04-24T15:47:17 Z vjudge1 Cities (BOI16_cities) C++17
100 / 100
 4664 ms 40400 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
const int K = 33;
const long long INF = 1e18;
vector<pair<int,int>> vec[N];
long long dis[N][K] , ans = INF;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> q;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    int n,k,m; cin >> n >> k >> m;
    int all = 1<<k;
    for (int i=0;i<all;i++) {
        for (int j=1;j<=n;j++) {
            dis[j][i] = INF;
        }
    }
    for (int i=0;i<k;i++) {
        int a; cin >> a;
        dis[a][1<<i] = 0;
    }
    while (m--) {
        int u,v,w; cin >> u >> v >> w;
        vec[u].push_back({w, v});
        vec[v].push_back({w, u});
    }
    for (int b1=1;b1<all;b1++) {
        for (int b2=1;b2<b1;b2<<=1) {
            if (b1&b2==0) continue;
            for (int i=1;i<=n;i++) {
                dis[i][b1] = min(dis[i][b1], dis[i][b2] + dis[i][b1^b2]);
            }
        }
        
        for (int i=1;i<=n;i++) {
            if (dis[i][b1]==INF) continue;
            q.push({dis[i][b1], i});
        }
        while (!q.empty()) {
            auto [dist,u] = q.top(); q.pop();
            for (auto [w,v]:vec[u]) {
                if (dis[v][b1] > dis[u][b1] + w) {
                    dis[v][b1] = dis[u][b1] + w;
                    q.push({dis[v][b1], v});
                }
            }
        }
    }
    for (int i=1;i<=n;i++) ans = min(ans, dis[i][all-1]);
    cout << ans;
    return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:30:22: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   30 |             if (b1&b2==0) continue;
      |                    ~~^~~

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1234 ms 37104 KB Output is correct
2 Correct 618 ms 36488 KB Output is correct
3 Correct 993 ms 32768 KB Output is correct
4 Correct 63 ms 13912 KB Output is correct
5 Correct 727 ms 40400 KB Output is correct
6 Correct 47 ms 13912 KB Output is correct
7 Correct 4 ms 6148 KB Output is correct
8 Correct 3 ms 5976 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5976 KB Output is correct
2 Correct 6 ms 5980 KB Output is correct
3 Correct 5 ms 6112 KB Output is correct
4 Correct 4 ms 3932 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2237 ms 36980 KB Output is correct
2 Correct 1329 ms 36584 KB Output is correct
3 Correct 1825 ms 32716 KB Output is correct
4 Correct 706 ms 29388 KB Output is correct
5 Correct 140 ms 16980 KB Output is correct
6 Correct 66 ms 13652 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3945 ms 37024 KB Output is correct
2 Correct 4452 ms 36980 KB Output is correct
3 Correct 2361 ms 36668 KB Output is correct
4 Correct 4664 ms 32896 KB Output is correct
5 Correct 1544 ms 29296 KB Output is correct
6 Correct 230 ms 16872 KB Output is correct
7 Correct 82 ms 13708 KB Output is correct