oj.uz

Submission #204837

# Submission time Handle Problem Language Result Execution time Memory
204837 2020-02-27T10:46:20 Z nickyrio Cities (BOI16_cities) C++17
100 / 100
 2322 ms 42380 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; ++preMask) if ((mask & preMask) == preMask) {
            int sufMask = mask ^ preMask;
            if (sufMask > preMask) continue;
            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 2808 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 23524 KB Output is correct
2 Correct 580 ms 22884 KB Output is correct
3 Correct 321 ms 16364 KB Output is correct
4 Correct 87 ms 11640 KB Output is correct
5 Correct 329 ms 20456 KB Output is correct
6 Correct 85 ms 11768 KB Output is correct
7 Correct 9 ms 2936 KB Output is correct
8 Correct 8 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 3064 KB Output is correct
4 Correct 10 ms 3028 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1155 ms 29944 KB Output is correct
2 Correct 1134 ms 28884 KB Output is correct
3 Correct 728 ms 22636 KB Output is correct
4 Correct 640 ms 21612 KB Output is correct
5 Correct 193 ms 13660 KB Output is correct
6 Correct 93 ms 13944 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2288 ms 42380 KB Output is correct
2 Correct 2322 ms 42348 KB Output is correct
3 Correct 2210 ms 41440 KB Output is correct
4 Correct 1489 ms 35180 KB Output is correct
5 Correct 1179 ms 27884 KB Output is correct
6 Correct 280 ms 15068 KB Output is correct
7 Correct 107 ms 14072 KB Output is correct