oj.uz

Submission #969155

# Submission time Handle Problem Language Result Execution time Memory
969155 2024-04-24T15:45:13 Z vjudge1 Cities (BOI16_cities) C++17
37 / 100
 4093 ms 41500 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 1;
const int K = 33;
const long long INF = 1e12;
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 1 ms 3676 KB Output is correct
3 Correct 1 ms 3676 KB Output is correct
4 Correct 1 ms 3676 KB Output is correct
5 Correct 1 ms 3676 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1218 ms 41348 KB Output is correct
2 Correct 519 ms 40724 KB Output is correct
3 Incorrect 52 ms 33728 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
15.0 / 15.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1977 ms 41500 KB Output is correct
2 Correct 1103 ms 40892 KB Output is correct
3 Incorrect 99 ms 33868 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4088 ms 41252 KB Output is correct
2 Correct 4093 ms 41164 KB Output is correct
3 Correct 2307 ms 40864 KB Output is correct
4 Incorrect 192 ms 33976 KB Output isn't correct
5 Halted 0 ms 0 KB -