Submission #1268032

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268032		ducdev	Cities (BOI16_cities)	C++17	100 / 100	1335 ms	40564 KiB

cities

// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;

#define all(x) (x).begin(), (x).end()

typedef long long ll;
typedef pair<int, int> ii;

const int MAX_N = 1e5;
const int MOD = 1e9 + 7;
const ll INF = 1e18;

int n, m, k;
int ver[5];
ll dp[1 << 5][MAX_N + 5];
vector<ii> adj[MAX_N + 5];

void dijkstra(ll *dist) {
    priority_queue<pair<ll, int>> pq;
    for (int u = 1; u <= n; u++)
        if (dist[u] != INF) pq.push(make_pair(-dist[u], u));

    while (!pq.empty()) {
        ll d = -pq.top().first;
        int u = pq.top().second;
        pq.pop();

        for (ii e : adj[u]) {
            int v = e.first, w = e.second;
            if (dist[u] + w < dist[v]) {
                dist[v] = dist[u] + w;
                pq.push(make_pair(-dist[v], v));
            };
        };
    };
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (fopen("MAIN.INP", "r")) {
        freopen("MAIN.INP", "r", stdin);
        freopen("MAIN.OUT", "w", stdout);
    };

    cin >> n >> k >> m;
    for (int i = 0; i < k; i++) cin >> ver[i];

    while (m--) {
        int u, v, w;
        cin >> u >> v >> w;
        adj[u].push_back(ii(v, w));
        adj[v].push_back(ii(u, w));
    };

    for (int mask = 0; mask < (1 << k); mask++) {
        for (int u = 0; u <= n; u++) dp[mask][u] = INF;
    };

    for (int i = 0; i < k; i++) dp[1 << i][ver[i]] = 0;

    for (int mask = 1; mask < (1 << k); mask++) {
        for (int u = 1; u <= n; u++) {
            for (int subMask = mask; subMask >= 0; subMask = (subMask - 1) & mask) {
                dp[mask][u] = min(dp[mask][u], dp[mask ^ subMask][u] + dp[subMask][u]);
                if (subMask == 0) break;
            };
        };
        dijkstra(dp[mask]);
    };

    cout << dp[(1 << k) - 1][ver[k - 1]];
};

Compilation message (stderr)

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

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