oj.uz

Submission #573253

# Submission time Handle Problem Language Result Execution time Memory
573253 2022-06-06T09:57:30 Z Arnch Cities (BOI16_cities) C++17
100 / 100
 3207 ms 54484 KB 
// oooo
/*
 har chi delet mikhad bebar ~
 gitar o ba khodet nabar! ~
 ;Amoo_Hasan;
*/

#include<bits/stdc++.h>
#pragma GCC optimize("O3,no-stack-protector,unroll-loops")
#pragma GCC target("avx2,fma")

using namespace std;

typedef long long ll;
typedef long double ld;

#define Sz(x) int((x).size())
#define All(x) (x).begin(), (x).end()
#define wtf(x) cout<<#x <<" : " <<x <<endl

constexpr ll inf = 1e18, N = 1e6 + 10, mod = 1e9 + 7, pr = 1000696969;

int n, m, k;
ll d[N][6], dp[N][6], sp[N];
vector<pair<int, ll> > G[N];
vector<int> vc;

inline void dijk(int x, int pos) {	
	for(int j = 0; j < n; j++) d[j][pos] = inf;
	set<pair<ll, int> > st;
	d[x][pos] = 0, st.insert({0, x});
	while(!st.empty()) {
		int p = st.begin() -> second; st.erase(st.begin());
		for(auto i : G[p]) {
			if(d[i.first][pos] > d[p][pos] + i.second) {
				st.erase({d[i.first][pos], i.first});
				d[i.first][pos] = d[p][pos] + i.second;
				st.insert({d[i.first][pos], i.first});
			}
		}
	}
}

inline void dojob(int ind1, int ind2, int ind3) {
	for(int i = 0; i < n; i++) dp[i][ind1] = inf;
	set<pair<int, ll> > st;
	vector<int> res;
	res.push_back(ind1), res.push_back(ind2), res.push_back(ind3);
/*	for(auto x : res) {
		for(int i = 0; i < n; i++) {
			sp[i] = d[i][x];
			st.insert({sp[i], i});
		}
		while(!st.empty()) {
			int p = st.begin() -> second; st.erase(st.begin());
			for(auto i : G[p]) {
				if(sp[i.first] > sp[p] + i.second) {
					st.erase({sp[i.first], i.first});
					sp[i.first] = sp[p] + i.second;
					st.insert({sp[i.first], i.first});
				}
			}
		}
		for(int i = 0; i < n; i++) {
			ll sum = d[i][ind1] + d[i][ind2] + d[i][ind3] - d[i][x];
			dp[i][ind1] = min(dp[i][ind1], sum + sp[i]);
		}
	}*/
	for(auto x : res) {
		for(auto x2 : res) {
			if(x == x2 || x > x2) continue;
			for(int i = 0; i < n; i++) {
				sp[i] = d[i][x] + d[i][x2];
				st.insert({sp[i], i});
			}
			while(!st.empty()) {
				int p = st.begin() -> second; st.erase(st.begin());
				for(auto i : G[p]) {
					if(sp[i.first] > sp[p] + i.second) {
						st.erase({sp[i.first], i.first});
						sp[i.first] = sp[p] + i.second;
						st.insert({sp[i.first], i.first});
					}
				}
			}
			for(int i = 0; i < n; i++) {
				ll sum = d[i][ind1] + d[i][ind2] + d[i][ind3] - d[i][x] - d[i][x2];
				dp[i][ind1] = min(dp[i][ind1], sum + sp[i]);
			}
		}
	}
}

int main() {
    ios :: sync_with_stdio(0), cin.tie(0);

	cin >>n >>k >>m;
	for(int i = 0; i < k; i++) {
		int v; cin >>v; v--, vc.push_back(v);
	}
	for(int i = 0; i < m; i++) {
		int u, v, w; cin >>u >>v >>w;
		u--, v--;
		G[u].push_back({v, w}), G[v].push_back({u, w});
	}	
	if(k == 2) {
		int u = vc[0], v = vc[1];
		dijk(u, 0);
		cout<<d[v][0] <<endl;
		return 0;
	}
	if(k == 3) {
		int pos = -1;
		for(auto x : vc) { pos++;
			dijk(x, pos);
		}
		ll ans = inf;
		for(int i = 0; i < n; i++) {
			ans = min(ans, d[i][0] + d[i][1] + d[i][2]);
		}
		cout<<ans;
		return 0;
	}
	ll ans = inf;
	
	if(k == 4) {
		for(int i = 0; i < 4; i++) {
			dijk(vc[i], i);
		}
		for(int i = 1; i < 4; i++) {
			int ind1 = -1, ind2 = -1;
			for(int j = 1; j < 4; j++) {
				if(j == i) continue;
				if(ind1 == -1) ind1 = j;
				else ind2 = j;
			}
			for(int j = 0; j < n; j++) {
				dp[j][ind1] = d[j][ind1] + d[j][ind2];
				dp[j][ind2] = 0;
			}
			set<pair<ll, int> > st;
			for(int j = 0; j < n; j++) {
				st.insert({d[j][0] + d[j][i], j});
				dp[j][ind2] = d[j][0] + d[j][i];
			}
			while(!st.empty()) {
				int p = st.begin() -> second; st.erase(st.begin());
				for(auto i : G[p]) {
					if(dp[i.first][ind2] > dp[p][ind2] + i.second) {
						st.erase({dp[i.first][ind2], i.first});
						dp[i.first][ind2] = dp[p][ind2] + i.second;
						st.insert({dp[i.first][ind2], i.first});
					}
				}
			}
			for(int j = 0; j < n; j++) {
				ans = min(ans, dp[j][ind2] + dp[j][ind1]);
			}
		}
		cout<<ans;
		return 0;
	}

	for(int i = 0; i < 5; i++) {
		dijk(vc[i], i);
	}
	for(int i = 1; i < 5; i++) {
		int ind1 = -1, ind2 = -1, ind3 = -1;
		for(int j = 1; j < 5; j++) {
			if(j == i) continue;
			if(ind1 == -1) ind1 = j;
			else if(ind2 == -1) ind2 = j;
			else ind3 = j;
		}
		dojob(ind1, ind2, ind3);
		for(int j = 0; j < n; j++) {
			dp[j][ind2] = 0;
		}
		set<pair<ll, int> > st;
		for(int j = 0; j < n; j++) {
			st.insert({d[j][0] + d[j][i], j});
			dp[j][ind2] = d[j][0] + d[j][i];
		}
		while(!st.empty()) {
			int p = st.begin() -> second; st.erase(st.begin());
			for(auto i : G[p]) {
				if(dp[i.first][ind2] > dp[p][ind2] + i.second) {
					st.erase({dp[i.first][ind2], i.first});
					dp[i.first][ind2] = dp[p][ind2] + i.second;
					st.insert({dp[i.first][ind2], i.first});
				}
			}
		}
		for(int j = 0; j < n; j++) {
			ans = min(ans, dp[j][ind2] + dp[j][ind1]);
		}
	}
	cout<<ans;

    return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23764 KB Output is correct
2 Correct 12 ms 23780 KB Output is correct
3 Correct 12 ms 23764 KB Output is correct
4 Correct 13 ms 23812 KB Output is correct
5 Correct 15 ms 23952 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 45316 KB Output is correct
2 Correct 402 ms 46012 KB Output is correct
3 Correct 129 ms 35872 KB Output is correct
4 Correct 79 ms 36128 KB Output is correct
5 Correct 205 ms 45308 KB Output is correct
6 Correct 76 ms 36064 KB Output is correct
7 Correct 15 ms 24020 KB Output is correct
8 Correct 14 ms 24020 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 24020 KB Output is correct
2 Correct 16 ms 24020 KB Output is correct
3 Correct 14 ms 24020 KB Output is correct
4 Correct 16 ms 23952 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 962 ms 53668 KB Output is correct
2 Correct 938 ms 52904 KB Output is correct
3 Correct 499 ms 46824 KB Output is correct
4 Correct 575 ms 45612 KB Output is correct
5 Correct 163 ms 37612 KB Output is correct
6 Correct 76 ms 38316 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3066 ms 54484 KB Output is correct
2 Correct 3027 ms 54472 KB Output is correct
3 Correct 3003 ms 53692 KB Output is correct
4 Correct 3207 ms 47564 KB Output is correct
5 Correct 1674 ms 45880 KB Output is correct
6 Correct 304 ms 37680 KB Output is correct
7 Correct 88 ms 38424 KB Output is correct