Submission #1278407

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278407		linhhnt11072010	Cities (BOI16_cities)	C++20	0 / 100	980 ms	39060 KiB

cities

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, m, k, u, v, c, kq[40][100009], a[10];
vector<pair<ll, ll> > vt[100009];
string s, s1;
void hkq(ll vt1, ll i1, ll j1){
	if(vt1>=s.size()){
		//if(s1 == s) return;
		ll ch = 0;
		for(int i = s1.size()-1;i>=0;i--){//s1.size()-1-
			if(s1[i] == '1') ch+=1ll<<i;
		}
		ll ch2 = i1-ch;
		//cout<<i1<<" "<<ch<<" "<<s1<<"\n";
		u = j1;//cout<<ch<<" "<<ch2<<" ";
		for(int i = 0;i<vt[u].size();i++){
			//cout<<i<<" "<<vt[u].size()<<"\n";
			v = vt[u][i].first, c = vt[u][i].second;
			//cout<<v<<" "<<c<<"\n";
			//
			if(kq[ch][u]!=1e18 and kq[ch2][v]!=1e18) kq[i1][j1] = min(kq[i1][j1], kq[ch][u]+c+kq[ch2][v]);
		}
		return;
	}
	if(s[vt1] == '1'){
		s1.push_back('1');
		hkq(vt1+1, i1, j1);
		s1.pop_back();
	}
	s1.push_back('0');
	hkq(vt1+1, i1, j1);
	s1.pop_back();
}
string pt(ll x){
    string p(k,'0');
    for(int i = 0;i<k;i++){
        if((x>>i)&1) p[i] = '1';
    }
    return p;
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin>>n>>k>>m;
	for(int i = 1;i<=k;i++) cin>>a[i];
	for(int i = 1;i<=m;i++){
		cin>>u>>v>>c;
		vt[u].push_back({v, c});
		vt[v].push_back({u, c});
	}
	for(int i = 1;i<=n;i++){
		vt[0].push_back({i, 0});
		//vt[i].push_back({0, 0});
	}
	for(int i = 1;i<=(1<<k)-1;i++){
		for(int j = 0;j<=n;j++) kq[i][j] = 1e18;
	}
	for(int i = 0;i<k;i++) kq[1<<i][a[i+1]] = 0;
	for(int i = 1;i<=(1<<k)-1;i++){
		for(int j = 1;j<=n;j++){
			s = pt(i);
			hkq(0, i, j);
		}
	}
	ll kqq = 1e18;
	for(int j = 1;j<=n;j++) kqq = min(kqq, kq[(1<<k)-1][j]);
	cout<<kqq;
}

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