Submission #335765

#TimeUsernameProblemLanguageResultExecution timeMemory
335765VROOM_VARUNCities (BOI16_cities)C++14
0 / 100
3399 ms76860 KiB
/* ID: varunra2 LANG: C++ TASK: cities */ #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "lib/debug.h" #define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__) #define debug_arr(...) \ cerr << "[" << #__VA_ARGS__ << "]:", debug_arr(__VA_ARGS__) #pragma GCC diagnostic ignored "-Wsign-compare" //#pragma GCC diagnostic ignored "-Wunused-parameter" //#pragma GCC diagnostic ignored "-Wunused-variable" #else #define debug(...) 42 #endif #define int long long #define EPS 1e-9 #define IN(A, B, C) assert(B <= A && A <= C) #define INF (int)1e15 #define MEM(a, b) memset(a, (b), sizeof(a)) #define MOD 1000000007 #define MP make_pair #define PB push_back #define all(cont) cont.begin(), cont.end() #define rall(cont) cont.end(), cont.begin() #define x first #define y second const double PI = acos(-1.0); typedef long long ll; typedef long double ld; typedef pair<int, int> PII; typedef map<int, int> MPII; typedef multiset<int> MSETI; typedef set<int> SETI; typedef set<string> SETS; typedef vector<int> VI; typedef vector<PII> VII; typedef vector<VI> VVI; typedef vector<string> VS; #define rep(i, a, b) for (int i = a; i < (b); ++i) #define trav(a, x) for (auto& a : x) #define sz(x) (int)(x).size() typedef pair<int, int> pii; typedef vector<int> vi; #pragma GCC diagnostic ignored "-Wsign-compare" // util functions int n, k, m; VVI dp; VVI dp1; vector<VII> adj; VI which; VVI pws; vector<bool> vis; // we can get submasks by doing base 3... void init() { dp.resize(1 << k); trav(x, dp) x.assign(n, INF); adj.resize(n); which.assign(n, -1); pws.resize(1 << k); } void dijk(int type) { // if we want to come from a neighbor priority_queue<PII, VII, greater<PII>> pq; for (int i = 0; i < n; i++) { pq.push(MP(dp[type][i], i)); } while (!pq.empty()) { auto xx = pq.top(); pq.pop(); int u = xx.y; if (vis[u]) continue; vis[u] = true; for (auto& x : adj[u]) { if (vis[x.x]) continue; if (dp[type][x.x] > xx.x + x.y) { dp[type][x.x] = xx.x + x.y; pq.push(MP(dp[type][x.x], x.x)); } } } } void dfs(int ind, int type) { if (vis[ind]) return; vis[ind] = true; for (auto& x : pws[type]) { dp[type][ind] = min(dp[type][ind], dp[x][ind] + dp[type ^ x][ind]); } for (auto& x : adj[ind]) { dfs(x.x, type); } } void gen() { int pw = 1; for (int i = 0; i < k; i++) pw *= 3; for (int i = 0; i < pw; i++) { VI vals(k, 0); int ind = 0; int cop = i; while (cop) { vals[ind++] = cop % k; cop /= k; } int val1 = 0; int val2 = 0; for (int i = 0; i < k; i++) { if (vals[i] >= 1) val1 |= (1 << i); if (vals[i] == 2) val2 |= (1 << i); pws[val1].PB(val2); } } } void process(int type) { vis.assign(n, false); dfs(0, type); vis.assign(n, false); dijk(type); } int32_t main() { // #ifndef ONLINE_JUDGE // freopen("cities.in", "r", stdin); // freopen("cities.out", "w", stdout); // #endif cin.sync_with_stdio(0); cin.tie(0); cin >> n >> k >> m; init(); for (int i = 0; i < k; i++) { int u; cin >> u; u--; which[u] = i; } for (int i = 0; i < m; i++) { int u, v, w; cin >> u >> v >> w; u--, v--; adj[u].PB(MP(v, w)); adj[v].PB(MP(u, w)); } for (int i = 0; i < n; i++) { dp[0][i] = 0; } for (int i = 0; i < n; i++) { if (~which[i]) dp[1 << which[i]][i] = 0; } dp1 = dp; gen(); for (int i = 1; i < (1 << k); i++) process(i); cout << *min_element(all(dp[(1 << k) - 1])) << '\n'; trav(x, dp) debug(x); return 0; }

Compilation message (stderr)

cities.cpp: In function 'int32_t main()':
cities.cpp:19:20: warning: statement has no effect [-Wunused-value]
   19 | #define debug(...) 42
      |                    ^~
cities.cpp:181:15: note: in expansion of macro 'debug'
  181 |   trav(x, dp) debug(x);
      |               ^~~~~
cities.cpp:33:11: warning: unused variable 'first' [-Wunused-variable]
   33 | #define x first
      |           ^~~~~
cities.cpp:50:31: note: in definition of macro 'trav'
   50 | #define trav(a, x) for (auto& a : x)
      |                               ^
cities.cpp:181:8: note: in expansion of macro 'x'
  181 |   trav(x, dp) debug(x);
      |        ^
#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...