제출 #1126637

#제출 시각아이디문제언어결과실행 시간메모리
1126637TVSownCities (BOI16_cities)C++20
0 / 100
1198 ms33240 KiB
///*** Sown_Vipro ***/// /// ->NHI QUOC GIA<- /// #include<bits/stdc++.h> using namespace std; //#pragma GCC optimize ("O3") //#pragma GCC optimize ("unroll-loops") //#pragma GCC target("popcnt") #define F first #define S second #define pb push_back #define pi pair<int, int> #define pii pair<int, pair<int, int> > #define FOR(i, a, b) for(int i = a; i <= b; ++i) #define REP(i, a, b) for(int i = a; i >= b; --i) #define all(s) s.begin(), s.end() #define szz(s) int(s.size()) const string NAME = "sown"; const int N = 1e6 + 5, MAX = 1e6, oo = 1e9 + 5, MOD = 1e9 + 7; void maxi(int &x, int y){ if(x < y) x = y; } void mini(int &x, int y){ if(x > y) x = y; }; void add(int &x, int y){ x += y; x += MOD * (x < 0); x -= MOD * (x >= MOD); }; int n, k, m; int trace[N], spe[N]; long long d[N], dp[(1 << 5) + 5]; vector<pi> e[N]; vector<int> s[(1 << 5) + 5]; void dt(vector<int> &ss, int S, int A, int B){ priority_queue<pair<long long, int> > pq; FOR(u, 1, n){ d[u] = 1e18; trace[u] = 0; } for(int u : ss){ d[u] = 0; pq.push({0, u}); } while(pq.size()){ int u = pq.top().S; long long du = -pq.top().F; pq.pop(); if(du != d[u]) continue; if(u == S) break; for(auto [v, w] : e[u]){ if(du + w < d[v]){ d[v] = du + w; trace[v] = u; pq.push({-du - w, v}); } } } if(dp[A] + d[S] >= dp[B]) return; dp[B] = dp[A] + d[S]; s[B].clear(); s[B] = s[A]; while(trace[S]){ s[B].pb(S); S = trace[S]; } } void solve(){ cin >> n >> k >> m; FOR(i, 1, k){ int u; cin >> u; spe[i] = u; dp[u] = 0; s[(1 << i - 1)].pb(u); } FOR(i, 1, m){ int u, v, w; cin >> u >> v >> w; e[u].pb({v, w}); e[v].pb({u, w}); } // FOR(i, 1, k) cout << spe[i] << "\n"; priority_queue<pi, vector<pi>, greater<pi> > pq; FOR(mask, 1, (1 << k) - 1){ if(s[mask].size()) continue; dp[mask] = 1e18; FOR(i, 1, k){ if(mask & (1 << i - 1)){ // cout << i << " " << spe[i] << "\n"; dt(s[mask ^ (1 << i - 1)], spe[i], mask ^ (1 << i - 1), mask); } } // cout << dp[mask] << "\n"; } cout << dp[(1 << k) - 1]; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); if(fopen((NAME + ".inp").c_str(), "r")){ freopen((NAME + ".inp").c_str(), "r", stdin); freopen((NAME + ".out").c_str(), "w", stdout); } int t = 1; // cin >> t; while(t--){ solve(); } }

컴파일 시 표준 에러 (stderr) 메시지

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