Submission #1105273

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105273		LOLOLO	Cities (BOI16_cities)	C++14	100 / 100	2105 ms	46132 KiB

cities

#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 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26