Submission #338131

#TimeUsernameProblemLanguageResultExecution timeMemory
338131KazamaHoangCities (BOI16_cities)C++14
0 / 100
251 ms17132 KiB
/* -> Written by <- ----------- K_A_Z_A_M_A ___________ _ | | (^_^) | | /( | )\ | |____|_|____| H O A N G */ #include <bits/stdc++.h> #define Task "" #define F first #define S second #define pb push_back #define bit(x, i) ((x >> (i)) & 1) #define inf 1e9 + 7 #define INF 1e18 + 7 #define ll long long #define pii pair <int, int> #define debug(x) cerr << #x << " is " << x << "\n"; using namespace std; const int MOD = 1e9 + 7; const int maxn = 1e5 + 5; int n, k, m; vector <pair<int, int>> ke[maxn]; pair <int, pair<int, int>> e[maxn]; bool dd[maxn]; int b[maxn]; int root[21]; int Get_Root(int u){ if (root[u] != u) root[u] = Get_Root(root[u]); return root[u]; } int Cal(int mask){ for (int i = 1; i <= n; ++ i) root[i] = i; int cnt = 0, res = 0; for (int i = 1; i <= m; ++ i){ int u = e[i].S.F; int v = e[i].S.S; int w = e[i].F; if (bit(mask, u-1) && bit(mask, v-1)){ u = Get_Root(u); v = Get_Root(v); if (u == v) continue; root[u] = v; res += w; } } for (int i = 1; i < k; ++ i){ int u = Get_Root(b[i]); for (int j = i + 1; j <= k; ++ j){ int v = Get_Root(b[j]); if (u != v) return inf; } } return res; } void Solve(){ cin >> n >> k >> m; for (int i = 1; i <= k; ++ i){ cin >> b[i]; } for (int i = 1; i <= m; ++ i){ int u, v, w; cin >> u >> v >> w; ke[u].pb({v, w}); ke[v].pb({u, w}); e[i] = {w, {u, v}}; } sort(e + 1, e + 1 + m); int ans = inf; for (int mask = 0; mask < (1 << n); ++ mask) ans = min(ans, Cal(mask)); cout << ans; } int main(){ ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); if(fopen(Task".inp", "r")){ freopen(Task".inp","r",stdin); freopen(Task".out","w",stdout); } int test_case = 1; // cin >> test_case; while (test_case --){ Solve(); } return 0; }

Compilation message (stderr)

cities.cpp: In function 'int Cal(int)':
cities.cpp:45:9: warning: unused variable 'cnt' [-Wunused-variable]
   45 |     int cnt = 0, res = 0;
      |         ^~~
cities.cpp: In function 'int main()':
cities.cpp:90:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   90 |         freopen(Task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:91:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   91 |         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...