Submission #734229

#	Time	Username	Problem	Language	Result	Execution time	Memory
734229		GrindMachine	Cities (BOI16_cities)	C++17	100 / 100	5566 ms	227624 KiB

cities

// Om Namah Shivaya

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x, y) ((x + y - 1) / (y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i, n) for(int i = 0; i < n; ++i)
#define rep1(i, n) for(int i = 1; i <= n; ++i)
#define rev(i, s, e) for(int i = s; i >= e; --i)
#define trav(i, a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a, b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a, b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x) 42
#endif

/*

refs:
https://youtu.be/BG4vAoV5kWw

spiderman algorithm
only works for k <= 5
for k > 5, use steiner tree dp

spiderman algo:
works when the chosen spanning tree is a caterpillar tree
i.e one main chain + 1-node branches from nodes in the main chain
only works for k <= 5

implement with modified dijkstra's

*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<pll> adj[N];

void solve(int test_case)
{
    ll n, k, m; cin >> n >> k >> m;
    vector<ll> a(k);
    rep(i, k) cin >> a[i];

    rep1(i, m) {
        ll u, v, w; cin >> u >> v >> w;
        adj[u].pb({v, w}), adj[v].pb({u, w});
    }

    ll dis[k][n + 5];
    rep(id, k) {
        ll s = a[id];
        priority_queue<pll, vector<pll>, greater<pll>> pq;
        pq.push({0, s});

        vector<bool> vis(n + 5);

        while (!pq.empty()) {
            auto [cost, u] = pq.top();
            pq.pop();

            if (vis[u]) conts;
            vis[u] = 1;
            dis[id][u] = cost;

            for (auto [v, w] : adj[u]) {
                pq.push({cost + w, v});
            }
        }
    }

    ll dp[n + 5][1 << k];
    memset(dp, -1, sizeof dp);

    priority_queue<array<ll, 3>, vector<array<ll, 3>>, greater<array<ll, 3>>> pq;
    pq.push({0, a[0], 1});

    while (!pq.empty()) {
        auto [cost, u, mask] = pq.top();
        pq.pop();

        if (dp[u][mask] != -1) conts;
        dp[u][mask] = cost;

        // continue main chain
        for (auto [v, w] : adj[u]) {
            pq.push({cost + w, v, mask});
        }

        // shoot web
        rep(id, k) {
            if (mask & (1 << id)) conts;
            ll v = a[id];
            ll w = dis[id][u];
            pq.push({cost + w, u, mask | (1 << id)});
        }
    }

    ll ans = inf2;
    rep1(u, n) {
        amin(ans, dp[u][(1 << k) - 1]);
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message (stderr)

cities.cpp: In function 'void solve(int)':
cities.cpp:130:16: warning: unused variable 'v' [-Wunused-variable]
  130 |             ll v = a[id];
      |                ^

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26