Submission #349161

#	Time	Username	Problem	Language	Result	Execution time	Memory
349161		ijxjdjd	Cities (BOI16_cities)	C++14	100 / 100	4547 ms	108600 KiB

cities

#include <bits/stdc++.h>

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define FR(i, N) for (int i = 0; i < int(N); i++)
using namespace std;

using ll = long long;

struct State {
    ll d;
    int msk, i;
    bool operator<(const State& rhs) const {
        return rhs.d < d;
    }
};
const int MAXN = (int)(1e5)+5;
const int MAXK = 5;
int st[MAXK];
int to[MAXN];
ll dist[MAXN][1<<MAXK];
const ll INF = (ll)(1e18);
vector<pair<int, ll>> adj[MAXN];
int main() {
	cin.tie(0);
	cin.sync_with_stdio(0);
	int N, k, M;
	cin >> N >> k >> M;
	FR(i, k) {
        cin >> st[i];
        st[i]--;
        to[st[i]] = i;
	}
	int cnt = k;
	FR(i, N){
        if (find(st, st+k, i) == (st + k)) {
            to[i] = cnt++;
        }
	}
	priority_queue<State> pq;
	FR(i, N) {
        FR(j, 1<<k) {
            dist[i][j] = INF;
        }
        if (i < k) {
            dist[i][1<<i] = 0;
            pq.push({0, 1<<i, i});
        }
	}
	FR(i, M) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        a = to[a];
        b = to[b];
        ll w;
        cin >> w;
        adj[a].push_back({b, w});
        adj[b].push_back({a, w});
	}
	while (pq.size()) {
        auto[d, msk, i] = pq.top(); pq.pop();
        if (msk == (1<<k)-1) {
            break;
        }
        if (dist[i][msk] == d) {
            for (auto[e, w] : adj[i]) {
                if (dist[e][msk] > d+w) {
                    dist[e][msk] = d+w;
                    pq.push({dist[e][msk], msk, e});
                }
            }
            for (int j = 0; j < k; j++) {
                if (dist[i][msk|(1<<j)] > dist[i][1<<j] + d) {
                    dist[i][msk|(1<<j)] = dist[i][1<<j] + d;
                    pq.push({dist[i][msk|(1<<j)], msk|(1<<j), i});
                }
            }
        }
	}
	ll ans = INF;
	FR(i, N) {
        ans = min(ans, dist[i][(1<<k)-1]);
	}
	cout << ans << '\n';
	return 0;
}

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:62:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   62 |         auto[d, msk, i] = pq.top(); pq.pop();
      |             ^
cities.cpp:67:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   67 |             for (auto[e, w] : adj[i]) {
      |                      ^

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