Submission #1190276

#TimeUsernameProblemLanguageResultExecution timeMemory
1190276sasdeCities (BOI16_cities)C++20
100 / 100
1209 ms42252 KiB
#include<bits/stdc++.h> #define task "cities" #define ii pair<int,int> #define iii pair<int,ii> #define iv pair<ii,ii> #define se second #define fi first #define int long long #define ffi fi.fi #define sfi se.fi #define sse se.se #define fse fi.se #define lt(i, c, d) for(int i = c; i <= d; ++i) #define fl(i, c, d) for(int i = d; i >= c; --i) #define pb push_back #define emb emplace_back #define emf emplace_front #define em emplace using namespace std; const int N=1e5+5,lg=20,mod=1e9+7; mt19937 rd(chrono::steady_clock::now().time_since_epoch().count()); int Rand(int u,int v){ return u+rd()%(v-u+1); } int n,k,m,b[5],dist[N][1<<5]; vector<ii>a[N]; void dijk(){ priority_queue<ii,vector<ii>,greater<ii>>p; for(int i=1;i<(1<<k);++i){ for(int z=1;z<=n;++z){ for(int j=i;(j^i)<j;j=(j-1)&i){ dist[z][i]=min(dist[z][i],dist[z][j]+dist[z][i^j]); } if(dist[z][i]!=1e18){ p.em(dist[z][i],z); } } while(!p.empty()){ int u=p.top().se; int w=p.top().fi; p.pop(); if(w>dist[u][i])continue; for(ii v:a[u]){ if(dist[v.fi][i]>dist[u][i]+v.se){ dist[v.fi][i]=dist[u][i]+v.se; p.em(dist[v.fi][i],v.fi); } } } } } void solve(){ cin >> n >> k >> m; for(int i=1;i<=n;++i){ for(int j=1;j<(1<<k);++j){ dist[i][j]=1e18; } } for(int i=1;i<=k;++i){ int u; cin >> u; dist[u][1<<(i-1)]=0; } for(int i=1;i<=m;++i){ int u,v,w; cin >> u >> v >> w; a[u].emb(v,w); a[v].emb(u,w); } dijk(); int res=1e18; for(int i=1;i<=n;++i){ res=min(res,dist[i][(1<<k)-1]); } cout<<res; } main() { srand(time(0)); 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 t=1; // cin >> t; while(t--){ solve(); cout<<'\n'; } }

Compilation message (stderr)

cities.cpp:77:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   77 | main()
      | ^~~~
cities.cpp: In function 'int main()':
cities.cpp:84:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   84 |       freopen(task".inp","r",stdin);
      |       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:85:14: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   85 |       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...