Submission #537817

#	Time	Username	Problem	Language	Result	Execution time	Memory
537817		new_acc	Cities (BOI16_cities)	C++14	100 / 100	2455 ms	40788 KiB

cities

#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=1e5+10;
const ll INF=1e18;
ll dp[1<<5][N];
vector<pair<int,int>> graf[N];
bitset<N>wyb;
bitset<N>vis;
int num[N];
void solve(){
	int n,k,m;
	cin>>n>>k>>m;
	int last=0;
	for(int i=0,a;i<k;i++){
		cin>>a;
		wyb[a]=1;
		num[a]=i;
		last=a;
	}
	for(int i=1,a,b,c;i<=m;i++){
		cin>>a>>b>>c;
		graf[a].push_back({b,c}),graf[b].push_back({a,c});
	}
	priority_queue<pair<ll,int>,vector<pair<ll,int> >,greater<pair<ll,int> > > ss;
	for(int i=1;i<(1<<k);i++){
		vi s;
		for(int wsk=1;wsk<=n;wsk++) dp[i][wsk]=(wyb[wsk] and ((1<<num[wsk])&i)?dp[i-(1<<num[wsk])][wsk]:INF);
		for(int j=0;j<k;j++) if((1<<j)&i) s.push_back(j);
		for(int j=1;j<(1<<s.size())-1;j++){
			int mask=0;
			for(int xd=0;xd<s.size();xd++) if((1<<xd)&j) mask+=(1<<s[xd]);
			for(int wsk=1;wsk<=n;wsk++) dp[i][wsk]=min(dp[i][wsk],dp[mask][wsk]+dp[i^mask][wsk]);
		}
		for(int j=1;j<=n;j++) ss.push({dp[i][j],j});
		while(ss.size()){
			pair<ll,int> v=ss.top();
			ss.pop();
			if(vis[v.se]) continue;
			dp[i][v.se]=v.fi;
			vis[v.se]=1;
			for(auto [u,c]:graf[v.se])
				if(!vis[u]) ss.push({c+v.fi,u});
		}
		vis.reset();
	}
	cout<<dp[(1<<k)-1][last]<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Compilation message (stderr)

cities.cpp: In function 'void solve()':
cities.cpp:36:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |    for(int xd=0;xd<s.size();xd++) if((1<<xd)&j) mask+=(1<<s[xd]);
      |                 ~~^~~~~~~~~
cities.cpp:46:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   46 |    for(auto [u,c]:graf[v.se])
      |             ^

• Subtask 1: 22 / 22
• Subtask 2: 14 / 14
• Subtask 3: 15 / 15
• Subtask 4: 23 / 23
• Subtask 5: 26 / 26