Submission #84876

#	Time	Username	Problem	Language	Result	Execution time	Memory
84876		atoiz	Cities (BOI16_cities)	C++14	100 / 100	2753 ms	42612 KiB

cities

#pragma GCC optimize ("Ofast")

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <queue>

using namespace std;

#define fi first
#define se second
#define int long long

const int INF = 1e17;
const int MAX = 100100;
int n, k, m;
int spec[5];
vector< pair<int, int> > G[MAX];
priority_queue< pair<int, int>, vector< pair<int, int> >, greater< pair<int, int> > > pq;

int ans[32][MAX];

int32_t main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k >> m;
	for (int i = 0; i < k; ++i) cin >> spec[i];
    for (int i = 0; i < m; ++i) {
        int u, v, c; cin >> u >> v >> c;
        G[u].push_back({c, v});
        G[v].push_back({c, u});
    }

    for (int i = 0; i < (1 << k); ++i) {
		for (int j = 1; j <= n; ++j) {
            ans[i][j] = INF;
		}
    }

    for (int i = 0; i < k; ++i) {
        ans[1 << i][spec[i]] = 0;
    }

	for (int mask = 1; mask < (1 << k); ++mask) {
        for (int i = 0; i < k; ++i) if ((mask >> i) & 1) {
			for (int u = 1; u <= n; ++u) {
				ans[mask][u] = min(ans[mask][u], ans[mask ^ (1 << i)][u] + ans[1 << i][u]);
			}
        }

        for (int u = 1; u <= n; ++u) pq.push({ans[mask][u], u});
        while (!pq.empty()) {
            pair<int, int> cur = pq.top(); pq.pop();
            if (ans[mask][cur.se] < cur.fi) continue;
            ans[mask][cur.se] = cur.fi;
            for (pair<int, int> e : G[cur.se]) {
                if (ans[mask][e.se] > cur.fi + e.fi) {
                    ans[mask][e.se] = cur.fi + e.fi;
                    pq.push({ans[mask][e.se], e.se});
                }
            }
        }
	}

	int final_ans = INF;
	for (int u = 1; u <= n; ++u) final_ans = min(final_ans, ans[(1 << k) - 1][u]);
	cout << final_ans;
}

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