제출 #839215

#제출 시각아이디문제언어결과실행 시간메모리
839215nnhzzzCities (BOI16_cities)C++14
100 / 100
1489 ms45544 KiB
// cre: Nguyen Ngoc Hung - Train VOI 2024 :> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <unordered_set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #include <cstring> #include <unordered_map> #include <cmath> #include <array> #include <cassert> #include <random> using namespace std; #define SORT_UNIQUE(v) sort(ALL(v)),(v).resize(unique(ALL(v))-(v).begin()) #define __nnhzzz__ signed main() #define BIT(i,j) ((i>>j)&1LL) #define MASK(i) (1LL<<i) #define RALL(x) (x).rbegin(),(x).rend() #define ALL(x) (x).begin(),(x).end() #define SZ(x) (int)(x).size() #define fi first #define se second #define INF 0x3f3f3f3f #define ll long long #define ull unsigned long long #define ld long double #define vi vector<int> #define vvi vector<vi> #define vvvi vector<vvi> #define vvvvi vector<vvvi> #define pii pair<int,int> #define vpii vector<pii> #define RESET(x,val) memset((x),(val),sizeof(x)) #define REPDIS(i,be,en,j) for(int i = (be); i<=(en); i+=j) #define REPD(i,be,en) for(int i = (be); i>=(en); i--) #define REP(i,be,en) for(int i = (be); i<=(en); i++) //-------------------------------------------------------------// const ll oo = 1e15; const int LOG = 20,MAXN = 1e5+7,N = 1e2+3; const int MOD = 1e9+7,MOD1 = 1e9+207,MOD2 = 1e9+407,MOD3 = 998244353; //-------------------------------------------------------------// template<typename T1, typename T2> bool mini(T1 &a, T2 b){if(a>b){a=b;return true;}return false;} template<typename T1, typename T2> bool maxi(T1 &a, T2 b){if(a<b){a=b;return true;}return false;} template<typename T> T gcd(T a, T b) { while(b) { a %= b; swap(a,b); } return a; } template<typename T> T lcm(T a, T b) { return a/gcd(a,b)*b; } /* ---------------------------------------------------------------- END OF TEMPLATE ---------------------------------------------------------------- Nguyen Ngoc Hung - nnhzzz Training for VOI24 gold medal ---------------------------------------------------------------- */ int spec[MAXN]; vpii adj[MAXN]; void solve(){ int n,k,m; cin >> n >> k >> m; REP(i,0,k-1){ cin >> spec[i]; --spec[i]; } REP(i,1,m){ int u,v,w; cin >> u >> v >> w; --u; --v; adj[u].emplace_back(v,w); adj[v].emplace_back(u,w); } // using T = tuple<int,int,ll>; // w,mask,u vector<vector<ll>> dis(MASK(k)|1,vector<ll>(n+3,oo)); REP(i,0,k-1){ dis[MASK(i)][spec[i]] = 0; } REP(state,0,MASK(k)-1){ for(int sub = (state-1)&state; sub!=0; sub = (sub-1)&state){ REP(i,0,n-1){ mini(dis[state][i],dis[sub][i]+dis[sub^state][i]); } } using T = pair<ll,int>; priority_queue<T,vector<T>,greater<T>> heap; REP(i,0,n-1){ if(dis[state][i]!=oo){ heap.emplace(dis[state][i],i); } } while(SZ(heap)!=0){ auto [w1,u] = heap.top(); heap.pop(); if(dis[state][u]!=w1){ continue; } for(auto [v,w]:adj[u]){ if(mini(dis[state][v],w1+w)){ heap.emplace(dis[state][v],v); } } } } ll res = oo; REP(i,0,n-1){ mini(res,dis[MASK(k)-1][i]); } cout << res; } __nnhzzz__{ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define name "test" if(fopen(name".inp","r")){ freopen(name".inp","r",stdin); freopen(name".out","w",stdout); } #define name1 "nnhzzz" if(fopen(name1".inp","r")){ freopen(name1".inp","r",stdin); freopen(name1".out","w",stdout); } int test = 1; while(test--){ solve(); } cerr << "\nTime elapsed: " << 1000*clock()/CLOCKS_PER_SEC << "ms\n"; return 0; }

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

cities.cpp: In function 'void solve()':
cities.cpp:121:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  121 |             auto [w1,u] = heap.top(); heap.pop();
      |                  ^
cities.cpp:125:22: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  125 |             for(auto [v,w]:adj[u]){
      |                      ^
cities.cpp: In function 'int main()':
cities.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  144 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  145 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:149:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |         freopen(name1".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:150:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  150 |         freopen(name1".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...