oj.uz

Submission #975375

# Submission time Handle Problem Language Result Execution time Memory
975375 2024-05-05T03:59:27 Z LOLOLO Cities (BOI16_cities) C++17
51 / 100
 2687 ms 46556 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] <= 1e12) {
                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 7 ms 27880 KB Output is correct
2 Correct 4 ms 27860 KB Output is correct
3 Correct 5 ms 27740 KB Output is correct
4 Correct 4 ms 27740 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 546 ms 45800 KB Output is correct
2 Correct 553 ms 45860 KB Output is correct
3 Correct 96 ms 32860 KB Output is correct
4 Correct 50 ms 35944 KB Output is correct
5 Correct 252 ms 44588 KB Output is correct
6 Correct 45 ms 35912 KB Output is correct
7 Correct 6 ms 27996 KB Output is correct
8 Correct 6 ms 27996 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27948 KB Output is correct
2 Correct 8 ms 27992 KB Output is correct
3 Correct 7 ms 27740 KB Output is correct
4 Correct 6 ms 27992 KB Output is correct

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1204 ms 46556 KB Output is correct
2 Correct 1189 ms 45176 KB Output is correct
3 Incorrect 183 ms 33120 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2669 ms 46048 KB Output is correct
2 Correct 2579 ms 46236 KB Output is correct
3 Correct 2687 ms 45328 KB Output is correct
4 Incorrect 352 ms 33264 KB Output isn't correct
5 Halted 0 ms 0 KB -