Submission #1276919

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276919		linhhnt11072010	Cities (BOI16_cities)	C++20	0 / 100	4423 ms	16712 KiB

cities

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll n, k, m, a[10], u, v, c, p1[200001], pp[10], kq = 1e18, mn;
vector<pair<ll, ll> > vt[200001];
vector<ll> vc;
void dfs(ll u, ll en, ll ans){
	if(p1[u] == 1 or en == u){
		if(en == u) mn = ans;
		return;
	}
	p1[u] = 1;
	for(int i = 0;i<vt[u].size();i++){
		dfs(vt[u][i].first, en, ans+vt[u][i].second);
	}
}
void hkq(ll vt){
	if(vt>k){
		ll p = 0;
		for(int i = 0;i<vc.size()-1;i++){
			for(int j = 1;j<=n;j++) p1[j] = 0;
			mn = 0;
			dfs(vc[i], vc[i+1], 0);
			p+=mn;
		}
		kq = min(kq, p);
	}
	for(int i = 1;i<=k;i++){
		if(pp[i] == 0){
			pp[i] = 1;
			vc.push_back(i);
			hkq(vt+1);
			pp[i] = 0;
			vc.pop_back();
		}
	}
}
int main(){
    ios_base::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});
    }
    hkq(1);
    cout<<kq;
}

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