Submission #1106348

#TimeUsernameProblemLanguageResultExecution timeMemory
1106348Zero_OPCities (BOI16_cities)C++14
100 / 100
5810 ms173052 KiB
#include <bits/stdc++.h> using namespace std; template<typename T> bool minimize(T& a, const T& b){ if(a > b){ return a = b, true; } return false; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); int N, K, M; cin >> N >> K >> M; vector<int> cities(K); for(int i = 0; i < K; ++i){ cin >> cities[i]; --cities[i]; } vector<vector<pair<int, int>>> adj(N); while(M--){ int u, v, w; cin >> u >> v >> w; --u, --v; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } const long long inf = 1e18; using node = tuple<long long, int, int>; priority_queue<node, vector<node>, greater<node>> pq; vector<vector<long long>> d(1 << K, vector<long long>(N, inf)); vector<vector<bool>> visited(1 << K, vector<bool>(N, false)); for(int i = 0; i < K; ++i){ d[1 << i][cities[i]] = 0; pq.push({d[1 << i][cities[i]], 1 << i, cities[i]}); } int full = (1 << K) - 1; while(!pq.empty()){ long long cur; int mask, u; tie(cur, mask, u) = pq.top(); pq.pop(); if(visited[mask][u]) continue; visited[mask][u] = true; for(auto [v, w] : adj[u]){ if(minimize(d[mask][v], d[mask][u] + w)){ pq.push({d[mask][v], mask, v}); } int not_mask = mask ^ full; for(int s = not_mask; s > 0; s = (s - 1) & not_mask){ if(minimize(d[mask | s][v], d[mask][u] + d[s][v] + w)){ pq.push({d[mask | s][v], mask | s, v}); } } } } long long ans = inf; for(int i = 0; i < N; ++i){ minimize(ans, d[(1 << K) - 1][i]); } cout << ans << '\n'; return 0; }

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:52:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   52 |         for(auto [v, w] : adj[u]){
      |                  ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...