oj.uz

Submission #253378

# Submission time Handle Problem Language Result Execution time Memory
253378 2020-07-27T19:43:25 Z Blagojce Cities (BOI16_cities) C++11
0 / 100
 6000 ms 14048 KB 
#include <bits/stdc++.h> 
#define fr(i, n, m) for(int i = (n); i < (m); i ++)
#define pb push_back
#define st first
#define nd second
#define pq priority_queue
#define all(x) begin(x), end(x)
#include <time.h>
#include <cmath>
 
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
 
const int i_inf = 1e9;
const ll inf = 1e18;
const ll mod = 1000000007;
const ld eps = 1e-13;
const ld pi  = 3.14159265359;
 
mt19937 _rand(time(NULL));
clock_t timer = clock();
const int mxn = 100005;
 
int n, k, m;
vector<pii> g[mxn];
vector<int> imp;
 
ll dist[6][mxn];
 
 
 
vector<int> code;
 
int deg[6];
 
ll decode(){
	fr(i, 0, k) deg[i] = 1;
	for(auto u : code){
		++deg[u];
	}
	set<int> leaves;
	fr(i, 0, k){
		if(deg[i] == 1) leaves.insert(i);
	}
	ll sum = 0;
	for(auto u : code){
		int leaf = *leaves.begin();
		leaves.erase(leaves.begin());
		
		sum += dist[leaf][imp[u]];
		--deg[u];
		if(deg[u] == 1) leaves.insert(u);
		
	}
	sum += dist[*leaves.begin()][imp[k-1]];
	return sum;
}
ll best = inf;
void generate_code(int pos){
	if(pos == k-2){
		best = min(best, decode()); 
	}
	else{
		fr(i, 0, k){
			code.pb(i);
			generate_code(pos+1);
			code.pop_back();
		}
	}
}
bool is_imp[mxn];
 
void solve(){
	cin >> n >> k >> m;
	imp.resize(k);
	fr(i, 0, k) cin >> imp[i];
	fr(i, 0, k) is_imp[--imp[i]] = true;
	
	fr(i, 0, m){
		int u, v, w;
		cin >> u >> v >> w;
		--u, --v;
		g[u].pb({v, w});
		g[v].pb({u, w});
	}
	bool vis[n];
	fr(i, 0, (int)imp.size()){
		memset(vis, false, sizeof(vis));
		fr(j, 0, n) dist[i][j] = inf;
		dist[i][imp[i]] = 0;
		pq<pii> Q;
		Q.push({0, imp[i]});
		while(!Q.empty()){
			int c = Q.top().nd;
			Q.pop();
			if(vis[c]) continue;
			vis[c] = true;
			for(auto e : g[c]){
				if(dist[i][c] + e.nd < dist[i][e.st]){
					dist[i][e.st] = dist[i][c] + e.nd;
					Q.push({-dist[i][e.st], e.st});
				} 
			}
		}
	}
	fr(i, 0, n){
		if(is_imp[i]) continue;
		imp.pb(i);
		fr(j, 0, k){
			dist[k][imp[j]] = dist[j][i];
		}
		++k;
		generate_code(0);
		--k;
		imp.pop_back();
	
	}
	generate_code(0);	
	cout << best << endl;
}
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	solve();
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Incorrect 4 ms 2688 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 729 ms 12296 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 60 ms 2936 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 4590 ms 13136 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 6058 ms 14048 KB Time limit exceeded
2 Halted 0 ms 0 KB -