Submission #1278404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1278404		linhhnt11072010	Cities (BOI16_cities)	C++20	0 / 100	6092 ms	38868 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 idx, ll mask, ll j){
    if(idx == k){
        for(int sub = mask; sub; sub = (sub-1)&mask){
            ll other = mask ^ sub;
            if(other == 0) continue;
            for(auto [v,c] : vt[j]){
                if(kq[sub][j] != 1e18 && kq[other][v] != 1e18)
                    kq[mask][j] = min(kq[mask][j], kq[sub][j] + c + kq[other][v]);
            }
        }
        return;
    }
    // ch?n bit idx
    hkq(idx+1, mask | (1LL<<idx), j);
    // không ch?n bit idx
    hkq(idx+1, mask, j);
}

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