Submission #1128594

#TimeUsernameProblemLanguageResultExecution timeMemory
1128594cbnhtmanhCities (BOI16_cities)C++20
100 / 100
2596 ms39792 KiB
#include <bits/stdc++.h> #define fi(i, a, b) for( int i = a; i <= b; i++ ) #define fid(i, a, b) for( int i = a; i >= b; i-- ) #define getbit(x, i) ((x>>i)&1) #define ll long long #define pb push_back #define pii pair<int,int> #define pli pair<ll,int> #define pll pair<ll,ll> #define st first #define nd second #define mp make_pair #define HTManh "" #define maxn 100009 #define endl '\n' using namespace std; int n, k, m; int imp[9]; vector<pii> a[100009]; vector<int> tt[1<<5]; ll L[1<<5][100009]; void dij(int mask) { priority_queue<pll> q; fi(i,1,n) { if (L[mask][i] < 1e18) q.push({-L[mask][i], i}); } while(q.size()) { int u = q.top().nd; q.pop(); for(int x: tt[mask]) L[mask^x][u] = min(L[mask^x][u], L[mask][u] + L[x][u]); for(pii tg: a[u]) { int v = tg.st, kc = tg.nd; if (L[mask][v] > L[mask][u] + kc) { L[mask][v] = L[mask][u] + kc; q.push({-L[mask][v], v}); } } } } int main() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); if (fopen(HTManh".inp", "r")) { freopen(HTManh".inp", "r", stdin); freopen(HTManh".out", "w", stdout); } cin >> n >> k >> m; fi(i,1,k) cin >> imp[i]; fi(i,1,m) { int x, y, z; cin >> x >> y >> z; a[x].pb({y, z}); a[y].pb({x, z}); } fi(x,1,(1<<k)-1) fi(y,1,(1<<k)-1) if ((x^y) == x+y) tt[x].pb(y); // fi(x,1,(1<<k)-1) fi(y,1,(1<<k)-1) if ((x^y) == x+y) cout << x << " " << y << endl; fi(x,1,(1<<k)-1) fi(i,1,n) L[x][i] = 1e18; fi(i,1,k) L[1<<(i-1)][imp[i]] = 0; fi(x,1,(1<<k)-1) dij(x); // fi(x,1,(1<<k)-1) // { // fi(i,1,n) cout << L[x][i] << " "; // cout << endl; // } ll res = 1e18; fi(i,1,n) res = min(res, L[(1<<k)-1][i]); cout << res << endl; }

Compilation message (stderr)

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