oj.uz

Submission #1105273

# Submission time Handle Problem Language Result Execution time Memory
1105273 2024-10-26T02:10:04 Z LOLOLO Cities (BOI16_cities) C++14
100 / 100
 2105 ms 46132 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 = mask;; in = (in - 1) & mask) {
            if (in * 2 < mask) {
                for (int i = 1; i <= n; i++) {
                    dp[i][mask] = min(dp[i][mask], dp[i][in] + dp[i][mask ^ in]);
                }
            }
          
          	if (in == 0)
            	break;
        }
 
        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 27728 KB Output is correct
2 Correct 4 ms 27728 KB Output is correct
3 Correct 5 ms 27728 KB Output is correct
4 Correct 4 ms 27900 KB Output is correct
5 Correct 4 ms 27884 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 393 ms 45716 KB Output is correct
2 Correct 402 ms 46044 KB Output is correct
3 Correct 232 ms 36728 KB Output is correct
4 Correct 49 ms 35992 KB Output is correct
5 Correct 173 ms 44404 KB Output is correct
6 Correct 42 ms 35952 KB Output is correct
7 Correct 6 ms 27984 KB Output is correct
8 Correct 7 ms 28240 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 27984 KB Output is correct
2 Correct 8 ms 27984 KB Output is correct
3 Correct 8 ms 27728 KB Output is correct
4 Correct 6 ms 27984 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1010 ms 45700 KB Output is correct
2 Correct 1026 ms 45856 KB Output is correct
3 Correct 656 ms 36720 KB Output is correct
4 Correct 421 ms 41224 KB Output is correct
5 Correct 128 ms 37320 KB Output is correct
6 Correct 49 ms 37516 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2105 ms 46132 KB Output is correct
2 Correct 1907 ms 45244 KB Output is correct
3 Correct 1927 ms 45992 KB Output is correct
4 Correct 1429 ms 36796 KB Output is correct
5 Correct 912 ms 41904 KB Output is correct
6 Correct 216 ms 37392 KB Output is correct
7 Correct 64 ms 37448 KB Output is correct