oj.uz

Submission #975376

# Submission time Handle Problem Language Result Execution time Memory
975376 2024-05-05T04:00:37 Z LOLOLO Cities (BOI16_cities) C++14
100 / 100
 2623 ms 41876 KB 
#include <bits/stdc++.h>
#define ll long long
using namespace std;
 
#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())
 
const int N = 1e5 + 100;
vector <pair <int, int>> ed[N];
ll dp[N][(1 << 5)];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    mem(dp, 0x3f);

    int n, k, m;
    cin >> n >> k >> m;

    for (int i = 0; i < k; i++) {
        int x;
        cin >> x;
        dp[x][(1 << i)] = 0;
    }

    for (int i = 1; i <= m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        ed[a].pb({b, c});
        ed[b].pb({a, c});
    }

    for (int mask = 0; mask < (1 << k); mask++) {
        for (int in = 0; in < mask; in++) {
            if ((in | mask) == mask && in * 2 < mask) {
                for (int i = 1; i <= n; i++) {
                    dp[i][mask] = min(dp[i][mask], dp[i][in] + dp[i][mask ^ in]);
                }
            }
        }

        priority_queue <pair <ll, int>, vector <pair <ll, int>>, greater <pair <ll, int>>> pq;

        for (int i = 1; i <= n; i++) {
            if (dp[i][mask] <= 1e16) {
                pq.push({dp[i][mask], i});
            }
        } 

        while (sz(pq)) {
            auto t = pq.top();
            pq.pop();
            if (dp[t.s][mask] < t.f)
                continue;

            for (auto x : ed[t.s]) {
                ll nxt = x.s + t.f;
                if (dp[x.f][mask] > nxt) {
                    dp[x.f][mask] = nxt;
                    pq.push({nxt, x.f});
                }
            }
        }
    }

    ll ans = dp[1][(1 << k) - 1];
    for (int i = 1; i <= n; i++) {
        ans = min(ans, dp[i][(1 << k) - 1]);
    }

    cout << ans << '\n';
}

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 550 ms 41784 KB Output is correct
2 Correct 595 ms 41784 KB Output is correct
3 Correct 292 ms 34576 KB Output is correct
4 Correct 54 ms 33148 KB Output is correct
5 Correct 258 ms 38652 KB Output is correct
6 Correct 44 ms 32520 KB Output is correct
7 Correct 6 ms 27992 KB Output is correct
8 Correct 6 ms 27992 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 27876 KB Output is correct
2 Correct 10 ms 27992 KB Output is correct
3 Correct 7 ms 27740 KB Output is correct
4 Correct 7 ms 27928 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1242 ms 41332 KB Output is correct
2 Correct 1275 ms 41088 KB Output is correct
3 Correct 746 ms 34620 KB Output is correct
4 Correct 605 ms 41240 KB Output is correct
5 Correct 121 ms 37328 KB Output is correct
6 Correct 54 ms 37516 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2600 ms 40932 KB Output is correct
2 Correct 2623 ms 41376 KB Output is correct
3 Correct 2526 ms 41340 KB Output is correct
4 Correct 1702 ms 34768 KB Output is correct
5 Correct 1100 ms 41876 KB Output is correct
6 Correct 191 ms 37408 KB Output is correct
7 Correct 62 ms 37456 KB Output is correct