제출 #1126531

#제출 시각아이디문제언어결과실행 시간메모리
1126531ntdaccodeCities (BOI16_cities)C++20
74 / 100
6098 ms165764 KiB
#include<bits/stdc++.h> using namespace std; const int M = 1e5 + 10; int n,m,k; long long f[M][1 << 5]; vector<pair<int,int>> ke[M]; priority_queue<tuple<long long ,int ,int >,vector<tuple<long long ,int ,int > > ,greater<tuple<long long ,int ,int > > > h; vector<int> submask[1 << 5][1 << 5]; long long kq=1e18; int dd[M]; void dij() { while(!h.empty()) { auto [val,mask,u] = h.top();h.pop(); if(val >= kq) { cout << kq; exit(0); } if(f[u][mask] != val) continue; for(pair<int,int> v : ke[u]) { dd[v.first] = (mask | dd[v.first]); for(int i : submask[mask][dd[v.first]]) { if(val + f[v.first][i^mask] + v.second < f[v.first][i]) { f[v.first][i] = val + f[v.first][i^mask] + v.second; if(i != (1<<k) - 1) h.push({f[v.first][i], i, v.first}); else kq = min(kq, f[v.first][i]); } } } } } int32_t main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define task "1" if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } cin >> n >> k >> m; for(int i = 0;i < (1 << k); i++) { for(int e = 0;e < (1 << k); e++) { for(int j = (1 << k) - 1;j >= 0; j--) if((i & j) == i && (j & e) == j) submask[i][e].push_back(j); } } for(int i = 1;i <= n; i++) { for(int j = 1;j < (1 << k); j++) f[i][j] = 1e18; } for(int i = 0;i < k; i++) { int x; cin >> x; h.push({0,1 << i,x}); f[x][1 << i] = 0; dd[x] = 1 << i; } for(int i = 1;i <= m; i++) { int u,v; long long w; cin >> u >> v >> w; ke[u].push_back({v,w}); ke[v].push_back({u,w}); } dij(); }

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

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