oj.uz

답안 #253114

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253114 2020-07-26T23:33:39 Z Adhyyan1252 Cities (BOI16_cities) C++11
100 / 100
 1723 ms 41200 KB 
#define NDEBUG
#include<bits/stdc++.h>
//12 48
using namespace std;

#define INF 1e17
#define ll long long

typedef pair<ll, int> ii;
template <typename T>
using vv = vector<vector<T> >;

struct edge{
	int u, v;
	ll c;
};

int n, k, m;
vector<int> h;
vv<int> g;
vector<edge> e;
vector<vector<ll> > dh;
void dijkstra1(int val){ //val is the index of the impp array
	int source = h[val];
	dh[val] = vector<ll>(n, INF);
	priority_queue<ii> q;
	q.push({0, source});
	while(!q.empty()){
		pair<ll, ll> t = q.top();
		q.pop();
		if(dh[val][t.second] != INF){
			assert(dh[val][t.second] <= -t.first);
			continue;
		}
		dh[val][t.second] = -t.first;
		for(int eid: g[t.second]){
			int next = e[eid].u + e[eid].v - t.second;
			if(dh[val][next] == INF){
				q.push({t.first - e[eid].c, next});
			}else{
				assert(dh[val][next] <= (-t.first + e[eid].c));
			}
		}
	}
}

vector<vector<vector<ll> > > dab;

signed main(){
	ios::sync_with_stdio(false); cin.tie(0);
	cin>>n>>k>>m;
	h.resize(k);
	for(int i = 0; i < k; i++){
		cin>>h[i]; h[i]--;
	}
	g.resize(n);
	for(int i = 0; i < m; i++){
		int a, b, c; cin>>a>>b>>c;
		a--, b--;
		e.push_back({a, b, c});
		g[a].push_back(i);
		g[b].push_back(i);
	}
	
	//find shortest path from all important to all others
	dh.resize(k);
	for(int i = 0; i < k; i++){
		dijkstra1(i);
	}
	//d[a][b][i] short distance from i to a and i to b
	dab = vector<vector<vector<ll> > > (k, vector<vector<ll> > (k, vector<ll>(n, INF)));
	for(int a = 0; a < k; a++){
		for(int b = a; b < k; b++){
			if(a == b){
				dab[a][a] = dh[a];
			}else{
				for(int i = 0; i < n; i++){
					dab[a][b][i] = dh[a][i] + dh[b][i];
				}
			}
		}	
	}
	
	//do multisource dijkstra from 
	for(int a = 0; a < k; a++){
		for(int b = a+1; b < k; b++){
			//make dab[a][b][i] the best value for i
			vector<int> vis(n, 0);
			priority_queue<ii> q;
			for(int i = 0; i < n; i++){
				q.push({-dab[a][b][i], i});
			}
			while(!q.empty()){
				ii t = q.top(); q.pop();
				if(vis[t.second]) {
					assert(-t.first >= dab[a][b][t.second]);
					continue;
				}
				vis[t.second] = 1;
				assert(dab[a][b][t.second] >= -t.first);
				dab[a][b][t.second] = -t.first;
				
				for(int eid: g[t.second]){
					int next = e[eid].u + e[eid].v - t.second;
					if(dab[a][b][next] > (-t.first + e[eid].c)){
						q.push({t.first - e[eid].c, next});
						assert(vis[next] == 0);
					}
				}
			}
		}
	}
	
	ll bestAns = LONG_LONG_MAX;
		//find answer
		
	if(k < 5){
		for(int i = 0; i < n; i++){
		vector<int> perm(k);
		for(int j = 0; j < k; j++) perm[j] = j;
		
		do{
			ll curAns = 0;
			for(int j = 0; j < k; j += 2){
				if(j == k-1){
					curAns += dab[perm[j]][perm[j]][i];
				}else{	
					ll fir = perm[j], sec = perm[j+1];
						if(fir > sec) swap(fir, sec);
					curAns += dab[fir][sec][i];
				}
			}
			bestAns = min(bestAns, curAns);
		}while(next_permutation(perm.begin(), perm.end()));
	}	
	}else{
			for(int c = 0; c < 5; c++){
				int f1 = c==0?1:0;
				for(int f2 = 0; f2 < 5; f2++){
					if(f2 == f1 || f2 == c) continue;
					
					int o1 = -1, o2 = -1;
					for(o1 = 0; o1 < 5; o1++) if(o1 != f1 && o1 != f2 && o1 != c) break;
					o2 = 10 - (c + f1 + f2 + o1);
					
					
					for(int i = 0; i < n; i++){
						assert(f1 < f2); assert(o1 < o2);
						bestAns = min(bestAns, dab[c][c][i] + dab[f1][f2][i] + dab[o1][o2][i]);
					}
					
				}
			}
		}	
	
	cout<<bestAns<<endl;
}

Subtask #1
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 855 ms 27348 KB Output is correct
2 Correct 636 ms 27244 KB Output is correct
3 Correct 363 ms 21884 KB Output is correct
4 Correct 216 ms 12976 KB Output is correct
5 Correct 383 ms 22808 KB Output is correct
6 Correct 165 ms 13136 KB Output is correct
7 Correct 4 ms 640 KB Output is correct
8 Correct 3 ms 512 KB Output is correct

Subtask #3
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 640 KB Output is correct
2 Correct 6 ms 640 KB Output is correct
3 Correct 3 ms 640 KB Output is correct
4 Correct 4 ms 512 KB Output is correct

Subtask #4
23.0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1133 ms 34624 KB Output is correct
2 Correct 1033 ms 34296 KB Output is correct
3 Correct 698 ms 28700 KB Output is correct
4 Correct 727 ms 23236 KB Output is correct
5 Correct 321 ms 13604 KB Output is correct
6 Correct 256 ms 13808 KB Output is correct

Subtask #5
26.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1723 ms 41164 KB Output is correct
2 Correct 1655 ms 41200 KB Output is correct
3 Correct 1477 ms 40840 KB Output is correct
4 Correct 957 ms 35664 KB Output is correct
5 Correct 1018 ms 24320 KB Output is correct
6 Correct 417 ms 13652 KB Output is correct
7 Correct 325 ms 13792 KB Output is correct