Submission #878392

#	Time	Username	Problem	Language	Result	Execution time	Memory
878392		manizare	Cities (BOI16_cities)	C++14	15 / 100	6084 ms	37496 KiB

cities

#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define int long long
#define sz(v) (int)v.size()
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 1e5 + 10 , inf = 1e18 , mod = 998244353 ;
int cnt= 1,  id[maxn] , dis[100][maxn] ,mark[maxn]  , n , m , k , A[maxn] , B[maxn] ;
vector<pii> G[maxn]; 
void dij(int r){
	priority_queue <pii> pq ;
	if(id[r] !=0)return ;
	id[r] = cnt ;
	for(int i = 1 ;i <= n ;i++){
		dis[cnt][i] = inf ;
		mark[i] =0 ;
	}
	dis[cnt][r] = 0 ;
	pq.push({0 , r}) ;
	while(pq.size()){
		int v = pq.top().S ; 
		pq.pop() ;
		if(mark[v] == 1)continue; 
		mark[v] = 1; 
		for(pii u : G[v]){
			if(dis[cnt][u.F] > dis[cnt][v]+u.S){
				dis[cnt][u.F] = dis[cnt][v] + u.S ;
				pq.push({-dis[cnt][u.F]  , u.F}) ;
			}
		}
	}
	cnt++;
}

int sl2(vector <int> a){
	return dis[id[a[0]]][a[1]] ;
}
int sl3(vector <int> a){
	int ans = inf ; 
	vector <int> vec ;
	for(int i =1 ; i <= n; i++){
		ans = min(ans , dis[id[a[0]]][i] + dis[id[a[1]]][i] + dis[id[a[2]]][i]);
	}
	return ans ;
}
vector <pair <pii ,int> > ed; 
int sl4(vector <int> a){
	for(int i = 1; i <= n; i++){
		A[i] = dis[id[a[0]]][i] + dis[id[a[1]]][i] ;
		B[i] = dis[id[a[2]]][i] + dis[id[a[3]]][i] ;
	}
	priority_queue<pii> pq ;
	for(int i = 1; i <= n; i++){
		pq.push({-A[i] , i}); 
		mark[i] =0 ; 
	}
	while(pq.size()){
		int v= pq.top().S ;
		pq.pop() ;
		if(mark[v] == 1)continue;
		mark[v] = 1; 
		for(pii u : G[v]){
			if(A[u.F] > A[v] + u.S){
				A[u.F] = A[v] + u.S; 
				pq.push({-A[u.F] , u.F}) ;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		pq.push({-B[i] , i});
		mark[i] = 0;
	}
	while(pq.size()){
		int v= pq.top().S ;
		pq.pop() ;
		if(mark[v] == 1)continue;
		mark[v] = 1; 
		for(pii u : G[v]){
			if(B[u.F] > B[v] + u.S){
				B[u.F] = B[v] + u.S; 
				pq.push({-B[u.F] , u.F}) ;
			}
		}
	}
	int ans =inf ; 
	for(int i = 1 ; i<= n; i++){
		int sm =0 ;
		ans = min(ans , A[i] + B[i]) ;
		for(int x : a){
			sm += dis[id[x]][i];
		}
		ans = min(ans , sm );
	}
	return ans ;
}
int sl44(vector <int> vec){
		int ans = inf ;
		for(int i =0 ; i < 4 ; i++){
			vector <int> vec2 ;
			int f  =inf ;
			for(int x : vec){
				if(x!=vec[i]){
					vec2.pb(x);
					f = min(f , dis[id[vec[i]]][x]);
				}
			}
			ans = min(ans , f + sl3(vec2)) ;
		}
		ans = min(ans , sl4(vec)) ;
		swap(vec[1] , vec[2]) ;
		ans = min(ans , sl4(vec)) ;
		swap(vec[1] , vec[3]) ;
		ans = min(ans , sl4(vec)) ;
	return ans ; 
}
int sl5(vector <int> a){
	for(int i = 1; i <= n; i++){
		A[i] = dis[id[a[0]]][i] + dis[id[a[1]]][i] ;
		B[i] = dis[id[a[2]]][i] + dis[id[a[3]]][i] ;
	}
	priority_queue<pii> pq ;
	for(int i = 1; i <= n; i++){
		pq.push({-A[i] , i}); 
		mark[i] =0 ; 
	}
	while(pq.size()){
		int v= pq.top().S ;
		pq.pop() ;
		if(mark[v] == 1)continue;
		mark[v] = 1; 
		for(pii u : G[v]){
			if(A[u.F] > A[v] + u.S){
				A[u.F] = A[v] + u.S; 
				pq.push({-A[u.F] , u.F}) ;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		pq.push({-B[i] , i});
		mark[i] = 0;
	}
	while(pq.size()){
		int v= pq.top().S ;
		pq.pop() ;
		if(mark[v] == 1)continue;
		mark[v] = 1; 
		for(pii u : G[v]){
			if(B[u.F] > B[v] + u.S){
				B[u.F] = B[v] + u.S; 
				pq.push({-B[u.F] , u.F}) ;
			}
		}
	}
	int ans =inf ; 
	for(int i = 1 ; i<= n; i++){
		int sm =0 ;
		ans = min(ans , A[i] + B[i] + dis[id[a[4]]][i]) ;
		for(int x : a){
			sm += dis[id[x]][i];
		}
		ans = min(ans , sm );
	}	
	for(int i =1 ; i <= n; i++){
		B[i] = dis[id[a[2]]][i] + dis[id[a[3]]][i] + dis[id[a[4]]][i];
		mark[i] =0 ;
		pq.push({-B[i] , i});
	}
	while(pq.size()){
		int v= pq.top().S ;
		pq.pop() ;
		if(mark[v] == 1)continue;
		mark[v] = 1; 
		for(pii u : G[v]){
			if(B[u.F] > B[v] + u.S){
				B[u.F] = B[v] + u.S; 
				pq.push({-B[u.F] , u.F}) ;
			}
		}
	}
	for(int i = 1; i <= n; i++){
		ans = min(ans , A[i] + B[i]);
	}
	return ans ;
}

signed main() {
    ios::sync_with_stdio(0); cin.tie(0);
	cin >> n>> k >> m ;
	int dd = 0;
	vector <int> vec; 
	for(int i =0 ; i < k ; i++){
		int f; 
		cin >> f ;vec.pb(f);
	}
	for(int i = 1; i <= m ;i++){
		int v, u  , c ;
		cin >> v >> u >> c ;
		ed.pb({{v,u} ,c});
		G[v].pb({u,c});
		G[u].pb({v,c}) ;
	}
	for(int x : vec)dij(x);vector <int> p ;
	for(int i =0 ; i < 5 ; i++)p.pb(i);
	int ans = inf ;
	for(int i =0 ; i < 5 ; i++){
		int f =0 ;
		for(int x : vec){
			if(x!=vec[i]){
				f = min(f , dis[id[vec[i]]][x]);
			}
		}
		ans = min(ans , sl44(vec) + f) ;
	}
	do{
		vector <int> vec2 ;
		for(int i =0 ; i < 5 ; i++){
			vec2.pb(vec[p[i]]) ;
		}
		ans = min(ans , sl5(vec2)) ;
	}while(next_permutation(all(p)));
	cout << ans << "\n" ;
}
/* 
 
 
*/

Compilation message (stderr)

cities.cpp: In function 'int main()':
cities.cpp:208:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  208 |  for(int x : vec)dij(x);vector <int> p ;
      |  ^~~
cities.cpp:208:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  208 |  for(int x : vec)dij(x);vector <int> p ;
      |                         ^~~~~~
cities.cpp:195:6: warning: unused variable 'dd' [-Wunused-variable]
  195 |  int dd = 0;
      |      ^~

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