oj.uz

Submission #204838

# Submission time Handle Problem Language Result Execution time Memory
204838 2020-02-27T10:47:39 Z nickyrio Cities (BOI16_cities) C++17
100 / 100
 2367 ms 42348 KB 
#include <bits/stdc++.h>

using namespace std;
#define long long long
#define pp pair<long, long>

const int N = 1e5 + 100;
const int K = 5;

long d[1 << K][N];
vector<pp> e[N];
int star[N];

void Min(long &a, long b){ a = (a > b ? b : a); }
const long inf = 2e16;

int main() {
    ios::sync_with_stdio(false); cin.tie(NULL);
    int n, k, m;
    cin >> n >> k >> m;
    priority_queue<pp> q;
    for (int i = 0; i < (1 << k); ++i) for (int j = 0; j < n; ++j) d[i][j] = inf;
    for (int i = 0; i < k; ++i) {
        int x; cin >> x;
        --x;
        d[1 << i][x] = 0;
    }
    for (int i = 0; i < m; ++i) {
        int u, v, c;
        cin >> u >> v >> c;
        --u, --v;
        e[u].push_back(pp(v, c));
        e[v].push_back(pp(u, c));
    }
    for (int mask = 0; mask < (1 << k); ++mask) {
        for (int preMask = 0; preMask <= mask / 2; ++preMask) if ((mask & preMask) == preMask) {
            int sufMask = mask ^ preMask;
            for (int i = 0; i < n; ++i) {
                Min(d[mask][i], d[preMask][i] + d[sufMask][i]);
            }
        }
        for (int i = 0; i < n; ++i) if (d[mask][i] != inf) q.emplace(-d[mask][i], i);
        while (!q.empty()) {
            int u = q.top().second;
            long dist = -q.top().first;
            q.pop();
            if (d[mask][u] != dist) continue;
         //   cerr << "Say " << mask << ' ' << u << ' ' << dist << '\n';
            for (auto t : e[u]) {
                int v = t.first;
                long c = t.second;
                if (d[mask][v] > d[mask][u] + c) {
                    d[mask][v] = d[mask][u] + c;
                    q.emplace(-d[mask][v], v);
             //       cerr << "To " << v << ' ' << d[mask][v] << '\n';
                }
            }
        }
    }
    long ans = *min_element(d[(1 << k) - 1], d[(1 << k) - 1] + n);
    cout << ans << '\n';
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2680 KB Output is correct
2 Correct 6 ms 2680 KB Output is correct
3 Correct 6 ms 2680 KB Output is correct
4 Correct 6 ms 2808 KB Output is correct
5 Correct 6 ms 2936 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 602 ms 23652 KB Output is correct
2 Correct 571 ms 22764 KB Output is correct
3 Correct 339 ms 16360 KB Output is correct
4 Correct 85 ms 11768 KB Output is correct
5 Correct 323 ms 20456 KB Output is correct
6 Correct 83 ms 11640 KB Output is correct
7 Correct 9 ms 2936 KB Output is correct
8 Correct 7 ms 2936 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 3064 KB Output is correct
2 Correct 11 ms 3064 KB Output is correct
3 Correct 9 ms 2936 KB Output is correct
4 Correct 10 ms 2936 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1183 ms 29800 KB Output is correct
2 Correct 1105 ms 28888 KB Output is correct
3 Correct 714 ms 22764 KB Output is correct
4 Correct 634 ms 21612 KB Output is correct
5 Correct 190 ms 13660 KB Output is correct
6 Correct 91 ms 14072 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2312 ms 42344 KB Output is correct
2 Correct 2367 ms 42348 KB Output is correct
3 Correct 2238 ms 41520 KB Output is correct
4 Correct 1515 ms 35184 KB Output is correct
5 Correct 1216 ms 27880 KB Output is correct
6 Correct 284 ms 14944 KB Output is correct
7 Correct 116 ms 14072 KB Output is correct