Submission #1280958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1280958		nguyenhuuhongquan	Cities (BOI16_cities)	C++20	100 / 100	2325 ms	44860 KiB

cities

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
#define ull unsigned long long
#define BIG __int128
#define fi first
#define se second
#define MASK(i) (1ll << i)
#define BIT(x, i) (((x) >> (i)) & 1)
#define sz(x) (int)(x).size()
#define debug cout << "NO ERROR", exit(0);
#define TASK "txt"
#define IOS ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
const int MOD = 1e9 + 7;
const int INF = 1e18;
const int LimN = 1e5 + 5;
const int LimM = 2e5 + 5;
void maximize(int &x, int y){
    x = max(x, y);
}
void minimize(int &x, int y){
    x = min(x, y);
}
void add(int &x, int y){
    x = (x % MOD + y % MOD) % MOD;
}
int n, k, m, a[10], dp[MASK(5)][LimN];
vector<pair<int, int>> adj[LimM];
void solve(){
    cin >> n >> k >> m;
    for (int i = 1; i <= k; i ++) cin >> a[i];
    memset(dp, 0x3f, sizeof dp);
    for (int i = 1; i <= m; i ++){
        int x, y, c; cin >> x >>  y >> c;
        adj[x].push_back({y, c});
        adj[y].push_back({x, c});
    }
    for (int i = 1; i <= n; i ++) dp[0][i] = 0;
    for (int i = 1; i <= k; i ++) dp[MASK(i - 1)][a[i]] = 0;
    for (int mask = 0; mask < MASK(k); mask ++){
        for (int submask = mask; ; submask = (submask - 1) & mask){
            for (int v = 1; v <= n; v ++){
                minimize(dp[mask][v], dp[submask][v] + dp[mask ^ submask][v]);
                // cout << mask << " " << submask << " " << (mask ^ submask) << "\n";
                // cout << dp[mask][v] << "\n";
            }
            if (submask == 0) break;
        }
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (int v = 1; v <= n; v ++) pq.push({dp[mask][v], v});
        while(!pq.empty()){
            auto [c, v] = pq.top(); pq.pop();
            // cout << v << "\n";
            for (auto x : adj[v]){
                int ncost = c + x.se;
                if (dp[mask][x.fi] > ncost){
                    dp[mask][x.fi] = ncost;
                    pq.push({ncost, x.fi});
                }
            }
        }
    }
    // for (int mask = 0; mask < MASK(5); mask ++){
    //     for (int i = 1; i <= n; i ++) cout << mask << " " << i << " " << dp[mask][i] << "\n";
    // }
    int ans = INF;
    for (int i = 1; i <= n; i ++) minimize(ans, dp[MASK(k) - 1][i]);
    cout << ans << "\n";

}
// Authors: Nguyen Huu Hong Quan from Tay Son Secondary school Da Nang
signed main(){
    IOS;
    if (fopen(TASK".inp", "r")){
        freopen(TASK".inp", "r", stdin);
        freopen(TASK".out", "w", stdout);
    }
    int Q = 1, NumTest = 0;
    //cin >> Q;
    for (int i = 1; i <= Q; i ++){
        if (NumTest) cout << "Case #" << i << ": ";
        solve();
    }
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:76:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:77:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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