Submission #487379

#TimeUsernameProblemLanguageResultExecution timeMemory
487379Koosha_mvCities (BOI16_cities)C++14
22 / 100
5769 ms48000 KiB
#include <bits/stdc++.h> using namespace std; #define erorp(x) cout<<#x<<"={"<<(x.F)<<" , "<<x.S<<"}"<<endl #define print(v,r) f(i,0,r) cout<<v[i]<<" "; cout<<endl #define eror(x) cout<<#x<<'='<<(x)<<endl #define f_(i,a,b) for(int i=a;i>=b;i--) #define f(i,a,b) for(int i=a;i<b;i++) #define nb(x) __builtin_popcount(x) #define maxm(a,b) a=max(a,b) #define minm(a,b) a=min(a,b) #define Add(x,y) x=(x+y)%mod #define lst(x) x[x.size()-1] #define sz(x) int(x.size()) #define mp make_pair #define ll long long #define pb push_back #define S second #define F first #define int ll const int N=2e5+99,K=5; const ll inf=1e15; int n,k,m,a[N],imp[N],col[N]; ll ans=inf,dp[N][(1<<K)]; vector<int> v[(1<<K)]; vector<pair<int,int> > g[N]; set<pair<ll,int> > s; void build(){ f(mask1,0,(1<<k)){ f(mask2,0,(1<<k)){ if(((mask1&mask2)==0)){ v[mask1].pb(mask2); } } } } void upd(int u,int mask,ll x){ if(dp[u][mask]<=x) return ; dp[u][mask]=x; } void solve(int mk){ s.clear(); f(i,1,n+1){ s.insert(mp(dp[i][mk],i)); } while(s.size()){ pair<ll,int> p=*s.begin(); int u=p.S; s.erase(p); f(i,0,g[u].size()){ if(dp[u][mk]+g[u][i].S<dp[g[u][i].F][mk]){ s.erase(mp(dp[g[u][i].F][mk],mk)); dp[g[u][i].F][mk]=dp[u][mk]+g[u][i].S; s.erase(mp(dp[g[u][i].F][mk],mk)); } } } f(i,1,n+1){ int u=i,mask=mk; f(i,0,g[u].size()){ f(j,0,v[mask].size()){ int nmask=v[mask][j]; upd(u,mask|nmask,dp[u][mask]+dp[g[u][i].F][nmask]+g[u][i].S); upd(g[u][i].F,mask|nmask,dp[u][mask]+dp[g[u][i].F][nmask]+g[u][i].S); } } } } main(){ ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0); fill(col,col+N,-1); cin>>n>>k>>m; build(); f(i,0,k){ cin>>imp[i]; col[imp[i]]=i; } f(i,0,m){ int u,v,c; cin>>u>>v>>c; g[u].pb(mp(v,c)); g[v].pb(mp(u,c)); } f(i,1,n+1){ f(mask,0,(1<<k)){ dp[i][mask]=inf; } } f(i,1,n+1){ if(col[i]==-1){ dp[i][0]=0; } else{ dp[i][(1<<col[i])]=0; } } f(mask,0,(1<<k)-1){ solve(mask); } f(i,1,n+1){ minm(ans,dp[i][(1<<k)-1]); } cout<<ans; }

Compilation message (stderr)

cities.cpp: In function 'void solve(long long int)':
cities.cpp:7:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   52 |   f(i,0,g[u].size()){
      |     ~~~~~~~~~~~~~~~            
cities.cpp:52:3: note: in expansion of macro 'f'
   52 |   f(i,0,g[u].size()){
      |   ^
cities.cpp:7:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   62 |   f(i,0,g[u].size()){
      |     ~~~~~~~~~~~~~~~            
cities.cpp:62:3: note: in expansion of macro 'f'
   62 |   f(i,0,g[u].size()){
      |   ^
cities.cpp:7:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 | #define f(i,a,b) for(int i=a;i<b;i++)
......
   63 |    f(j,0,v[mask].size()){
      |      ~~~~~~~~~~~~~~~~~~        
cities.cpp:63:4: note: in expansion of macro 'f'
   63 |    f(j,0,v[mask].size()){
      |    ^
cities.cpp: At global scope:
cities.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main(){
      | ^~~~
#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...