Submission #1279891

#TimeUsernameProblemLanguageResultExecution timeMemory
1279891shidou26Cities (BOI16_cities)C++20
100 / 100
1703 ms70288 KiB
#include <bits/stdc++.h> using namespace std; #ifdef KURUMI #include "algo/debug.h" #endif #define endl '\n' #define fi first #define se second #define sz(v) (int)v.size() #define all(v) v.begin(), v.end() #define filter(v) v.resize(unique(all(v)) - v.begin()) #define dbg(x) "[" #x << " = " << x << "]" mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); template<typename T1, typename T2> T2 rand(T1 l, T2 r) { return uniform_int_distribution<T2>(l, r)(rng); } template<typename T1, typename T2> T2 wrand(T1 l, T2 r, int seed) { if(seed == 0) return rand(l, r); else return (seed > 0 ? max(rand(l, r), wrand(l, r, seed - 1)) : min(rand(l, r), wrand(l, r, seed + 1))); } template<typename T> bool maximize(T &a, T b) { if(a < b) { a = b; return true; }else return false; } template<typename T> bool minimize(T &a, T b) { if(a > b) { a = b; return true; }else return false; } typedef long long ll; typedef long double ldb; typedef pair<int, int> pii; typedef pair<ll, int> pli; typedef pair<ll, ll> pll; typedef tuple<int, int, int> tp3; const int N = 2e5 + 3; int n, k, m; vector<int> imp; vector<pii> adj[N]; void input() { cin >> n >> k >> m; imp.resize(k); for(int i = 0; i < k; i++) { cin >> imp[i]; } for(int i = 1; i <= m; i++) { int u, v, w; cin >> u >> v >> w; adj[u].emplace_back(v, w); adj[v].emplace_back(u, w); } } const ll INF = 0x3f3f3f3f3f3f3f3f; ll dp[N][1 << 5 | 3]; void process() { memset(dp, 0x3f, sizeof(dp)); for(int mask = 1; mask < (1 << k); mask++) { if(__builtin_popcount(mask) == 1) { int i = 31 - __builtin_clz(mask); dp[imp[i]][1 << i] = 0; } for(int submask = mask; submask > 0; submask = (submask - 1) & mask) { for(int i = 1; i <= n; i++) { minimize(dp[i][mask], dp[i][submask] + dp[i][mask ^ submask]); } } priority_queue<pli, vector<pli>, greater<pli>> pq; for(int i = 1; i <= n; i++) if(dp[i][mask] != INF) { pq.emplace(dp[i][mask], i); } while(!pq.empty()) { ll cost; int u; tie(cost, u) = pq.top(); pq.pop(); if(cost > dp[u][mask]) continue; for(auto [v, w] : adj[u]) { if(minimize(dp[v][mask], dp[u][mask] + w)) { pq.emplace(dp[v][mask], v); } } } } ll answer = INF; for(int i = 1; i <= n; i++) { minimize(answer, dp[i][(1 << k) - 1]); } cout << answer << endl; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); #define task "Deeto" if(fopen(task".inp", "r")) { freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } int testcase = 1; // cin >> testcase; for(int i = 1; i <= testcase; i++) { input(); process(); } cerr << "Saa, watashtachi no deeto hajimemashou" << endl; cerr << "Atarashii kiseki wo koko kara hajimeru shining place nee mou ichido kimi to..." << endl; return 0; }

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:115:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  115 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:116:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  116 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#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...