Submission #1105283

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105283		thangdz2k7	Cities (BOI16_cities)	C++17	100 / 100	748 ms	42312 KiB

cities

// author : thembululquaUwU
// 3.9.2024

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

using namespace std;
using ll = long long;
using ii = pair <int, int>;
using lli = pair <ll, int>;
using vi = vector <int>;

const int N = 1e5 + 5;
const int mod = 1e9 + 7;
const ll inf = 1e18;
const int LG = 4;
const int mx = (1 << LG);

void maxl(auto &a, auto b) {a = max(a, b);}
void minl(auto &a, auto b) {a = min(a, b);}

int n, m, k, T, a[LG];
pair <int, int> trace[mx][N];
vector <ii> adj[N];
ll d[mx][N];
priority_queue <lli, vector <lli>, greater <lli>> pq;

#define Mask(i)  (1 << (i))
#define Bit(x, i)  ((x) >> (i) & 1)
#define bp __builtin_popcount
#define bpll __builtin_popcountll

struct Edge{
    int u, v, mask;
};

vector <Edge> ans;

void dfs(int mask, int u){
    auto [m1, m2] = trace[mask][u];
    if (!m1) return;
    if (m1 == mask){
        ans.push_back({m2, u, mask});
        dfs(m1, m2);
    }
    else {
        dfs(m1, u);
        dfs(m2, u);
    }
}

void solve(){
    cin >> n >> k >> m;
    for (int i = 0; i < k; ++ i) cin >> a[i];
    T = a[k - 1]; -- k;
    while (m --){
        int u, v, w; cin >> u >> v >> w;
        adj[u].pb({w, v});
        adj[v].pb({w, u});
    }

    int tae = (1 << k);
    for (int mask = 1; mask < tae; ++ mask){
        for (int i = 1; i <= n; ++ i) d[mask][i] = inf;
        if (bp(mask) == 1) {
            d[mask][a[__lg(mask)]] = 0;
            trace[mask][a[__lg(mask)]] = {0, 0};
        }
        for (int i = 1; i <= n; ++ i){
            for (int j = (mask - 1) & mask; j; j = (j - 1) & mask){
                if (d[mask][i] > d[j][i] + d[mask - j][i]){
                    d[mask][i] = d[j][i] + d[mask - j][i];
                    trace[mask][i] = {j, mask - j};
                }
            }
            pq.push({d[mask][i], i});
        }

        while (pq.size()){
            auto [du, u] = pq.top(); pq.pop();
            if (du != d[mask][u]) continue;
            for (auto [w, v] : adj[u]){
                if (d[mask][v] > du + w){
                    d[mask][v] = du + w;
                    trace[mask][v] = {mask, u};
                    pq.push({d[mask][v], v});
                }
            }
        }
    }

    cout << d[tae - 1][T] << endl;
//    dfs(tae - 1, T);
//    reverse(ans.begin(), ans.end());
//    cout << ans.size() << endl;
//    for (auto [u, v, mask] : ans){
//        for (int i = 0; i < k; ++ i) cout << Bit(mask, i);
//        cout << ' ' << u << ' ' << v << endl;
//    }
}

int main(){
    if (fopen("taxi.inp", "r")){
        freopen("taxi.inp", "r", stdin);
        freopen("taxi.out", "w", stdout);
    }
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int t = 1; // cin >> t;
    while (t --) solve();
    return 0;
}

Compilation message (stderr)

cities.cpp:22:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   22 | void maxl(auto &a, auto b) {a = max(a, b);}
      |           ^~~~
cities.cpp:22:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   22 | void maxl(auto &a, auto b) {a = max(a, b);}
      |                    ^~~~
cities.cpp:23:11: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void minl(auto &a, auto b) {a = min(a, b);}
      |           ^~~~
cities.cpp:23:20: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   23 | void minl(auto &a, auto b) {a = min(a, b);}
      |                    ^~~~
cities.cpp: In function 'int main()':
cities.cpp:107:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  107 |         freopen("taxi.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:108:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  108 |         freopen("taxi.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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