Submission #1281039

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281039		dang_minh_duc	Cities (BOI16_cities)	C++20	100 / 100	1798 ms	42400 KiB

cities

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define fi first
#define se second
#define unmap unordered_map
#define unset unordered_set
using namespace std;
const int dx[4]{-1, 0, 1, 0}, dy[4]{0, 1, 0, -1}; //0: Up  1: Right  2: Down  3: Left
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool minimize(X &x, const Y &y) {
         if (x > y) {
            x = y;
            return true;
         }
         return false;
    }
template<class X, class Y>
    void setvaluable(X &x, const Y &y) {
        if (x==-1 || x > y) x = y;
    }

const int LimN=1e5+5, INF=1e18;
int n, m, k, a[10], u, v, w, dp[LimN][1<<5], ans=INF;
vector<pair<int,int>>adj[LimN];
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>>pq;
void solve()
{
    cin >> n >> k >> m;
    for (int i=0;i<k;i++) cin >> a[i];
    while (m--) {
        cin >> u >> v >> w;
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }
    for (int j=1;j<(1<<k);j++) {
        for (int i=1;i<=n;i++) {
            dp[i][j]=INF;
            int cnt=__builtin_popcount(j), idx=__builtin_ctz(j);
            if (cnt==1 && a[idx]==i) dp[i][j]=0;
            else if (cnt>1) {
                for (int sub=(j-1)&j;sub;sub=(sub-1)&j) {
                    for (const pair<int,int> &v:adj[i]) {
                        minimize(dp[i][j], dp[v.fi][sub]+dp[i][j^sub]+v.se);
                    }
                }
            }
        }
        for (int i=1;i<=n;i++) pq.push({dp[i][j], i});
        while (!pq.empty()) {
            auto [w, u]=pq.top();
            pq.pop();
            if (w>dp[u][j]) continue;
            for (auto [v, weight]:adj[u]) {
                if (dp[v][j]>dp[u][j]+weight) {
                    dp[v][j]=dp[u][j]+weight;
                    pq.push({dp[v][j], v});
                }
            }
        }
    }
    for (int i=1;i<=n;i++) minimize(ans, dp[i][(1<<k)-1]);
    cout << ans;
}
signed main() {
    ios_base::sync_with_stdio(false);cin.tie(0);
    int numtest=1; //cin >> numtest;
    while (numtest--) {solve();}
    return 0;
}

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