Submission #1190163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190163		PieArmy	Cities (BOI16_cities)	C++20	100 / 100	1511 ms	42244 KiB

cities

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define fr first
#define sc second
#define endl '\n'
const ll inf=2000000000000000005;

int n,k,m;
vector<pair<int,ll>>komsu[100023];
ll dp[100023][32];

int main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);
	cin>>n>>k>>m;
	for(int i=1;i<=n;i++){
		dp[i][0]=0;
		for(int j=1;j<(1<<k);j++){
			dp[i][j]=inf;
		}
	}
	for(int i=0;i<k;i++){
		int x;cin>>x;
		dp[x][1<<i]=0;
	}
	for(int i=1;i<=m;i++){
		int x,y,c;cin>>x>>y>>c;
		komsu[x].pb({y,c});
		komsu[y].pb({x,c});
	}
	priority_queue<pair<ll,int>>pq;
	for(int i=1;i<(1<<k);i++){
		for(int l=1;l<=n;l++){
			for(int j=i;(j^i)<j;j=(j-1)&i){
				dp[l][i]=min(dp[l][i],dp[l][j]+dp[l][j^i]);
			}
			if(dp[l][i]!=inf)pq.push({-dp[l][i],l});
		}
		while(pq.size()){
			int pos=pq.top().sc;
			ll cos=-pq.top().fr;
			pq.pop();
			if(cos==dp[pos][i])
			for(auto&x:komsu[pos]){
				if(cos+x.sc<dp[x.fr][i]){
					dp[x.fr][i]=cos+x.sc;
					pq.push({-dp[x.fr][i],x.fr});
				}
			}
		}
	}
	ll res=inf;
	for(int i=1;i<=n;i++){
		res=min(res,dp[i][(1<<k)-1]);
	}
	cout<<res<<endl;
}

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