oj.uz

Submission #708175

# Submission time Handle Problem Language Result Execution time Memory
708175 2023-03-11T08:46:44 Z phamduchung Cities (BOI16_cities) C++14
100 / 100
 1742 ms 71668 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pii pair<long long, int>
const ll N = 1e5+8;
const ll inf = 1e9 + 7;
int n, k, m;
vector<int> imp;
vector<pii> adj[N];
ll f[1<<6][N];
priority_queue<pii, vector<pii>, greater<pii>> pq;

void dijkstra(ll f[N]) {
    for (int i = 1; i <= n; i++) {
        if (f[i] < 1e16) pq.push({f[i], i});
    }

    while (!pq.empty()) {
        ll d;
        int u;
        tie(d, u) = pq.top();
        pq.pop();
        if (d != f[u]) continue;
        for (auto e : adj[u]) {
            int v, w;
            tie(v, w) = e;
            if (f[v] > d + w) {
                f[v] = d + w;
                pq.push({f[v], v});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    memset(f, inf, sizeof(f));
    memset(f[0], 0, sizeof(f[0]));
    cin >> n >> k >> m;
    for (int i = 1; i <= k; i++) {
        int tmp;
        cin >> tmp;
        imp.push_back(tmp);
        f[1 << (i - 1)][tmp] = 0;
    }
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int mask = 1; mask < (1 << k); mask++) {
        for (int pos = 0; pos < k; pos++) {
            if (!((mask >> pos) & 1)) continue;
            for (int i = 1; i <= n; i++) {
                f[mask][i] = min(f[mask][i], f[mask ^ (1 << pos)][i] + f[(1 << pos)][i]);
            }
        }

        dijkstra(f[mask]);
    }
    cout << *min_element(f[(1 << k) - 1] + 1, f[(1 << k) - 1] + n + 1);
    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 52692 KB Output is correct
2 Correct 20 ms 52708 KB Output is correct
3 Correct 21 ms 52752 KB Output is correct
4 Correct 21 ms 52720 KB Output is correct
5 Correct 20 ms 52748 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 473 ms 71552 KB Output is correct
2 Correct 458 ms 70700 KB Output is correct
3 Correct 287 ms 62272 KB Output is correct
4 Correct 82 ms 65232 KB Output is correct
5 Correct 260 ms 71668 KB Output is correct
6 Correct 79 ms 65124 KB Output is correct
7 Correct 23 ms 52948 KB Output is correct
8 Correct 24 ms 52832 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 52820 KB Output is correct
2 Correct 26 ms 52900 KB Output is correct
3 Correct 23 ms 52812 KB Output is correct
4 Correct 23 ms 52904 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 919 ms 71588 KB Output is correct
2 Correct 970 ms 70596 KB Output is correct
3 Correct 543 ms 62300 KB Output is correct
4 Correct 506 ms 69616 KB Output is correct
5 Correct 158 ms 66096 KB Output is correct
6 Correct 85 ms 67308 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1736 ms 71620 KB Output is correct
2 Correct 1742 ms 71488 KB Output is correct
3 Correct 1604 ms 70548 KB Output is correct
4 Correct 1139 ms 62296 KB Output is correct
5 Correct 951 ms 69564 KB Output is correct
6 Correct 232 ms 66364 KB Output is correct
7 Correct 99 ms 67320 KB Output is correct