Submission #1193255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1193255		_rain_	Cities (BOI16_cities)	C++20	36 / 100	597 ms	71780 KiB

cities

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N=(int)2e5;
const int K=5;
vector<pair<int,int>>ke[N+2];
LL d[K+2][N+2]={};
LL cost[N+2][1<<K];
int u[N+2],v[N+2],c[N+2],vert[N+2]={};
vector<int>adj[1<<K];
int n,k,m;

void add_canh(int u,int v,int c){
	ke[u].push_back({v,c});
	ke[v].push_back({u,c});
	return;
}

struct Node{
	LL cost;
	int u,mask;
	bool operator < (const Node&other) const{
		return cost>other.cost;
	}
};

void djisktra(int id){
	memset(d[id],0x3f,sizeof d[id]);
	d[id][vert[id]]=0;
	priority_queue<pair<LL,int>,vector<pair<LL,int>>,greater<pair<LL,int>>>q;
	q.push({d[id][vert[id]],vert[id]});
	while (q.size()){
		int u=q.top().second;
		LL cost=q.top().first;
		q.pop();
		if (cost!=d[id][u]) continue;
		for(auto&v:ke[u]){
			if (d[id][v.first]>d[id][u]+v.second){
				d[id][v.first]=d[id][u]+v.second;
				q.push({d[id][v.first],v.first});
			}
		}
	}
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	//freopen("main.inp","r",stdin);
	
	cin>>n>>k>>m;
	for(int i=0;i<k;++i) cin>>vert[i];
	for(int i=1;i<=m;++i){
		cin>>u[i]>>v[i]>>c[i];
		add_canh(u[i],v[i],c[i]);
	}
	for(int i=0;i<k;++i) djisktra(i);
	memset(cost,0x3f,sizeof cost);
	for(int mask=0;mask<(1<<k);++mask){
		for(int submask=1;submask<(1<<k);++submask){
			if ((mask&submask)==0) adj[mask].push_back(submask);
		}
	}
	for(int mask=0;mask<(1<<k);++mask){
		for(int i=1;i<=n;++i){
			cost[i][mask]=0;
			for(int j=0;j<k;++j){
				if ((mask>>j)&1){
					cost[i][mask]+=d[j][i];
				}
			}
		}
	}
	
	for(int mask=0;mask<(1<<k);++mask){
		for(int u=1;u<=n;++u){
			for(auto&v:ke[u]){
				cost[v.first][mask]=min(cost[v.first][mask],cost[u][mask]+v.second);
				for(auto&x:adj[mask]){
					cost[v.first][mask|x]=min(cost[v.first][mask|x],cost[u][mask]+v.second+cost[v.first][x]);
				}
			}
		}
	}
	LL ans=(LL)1e18;
	for(int i=1;i<=n;++i) ans=min(ans,cost[i][(1<<k)-1]);
	cout<<ans;
}

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