oj.uz

Submission #957144

# Submission time Handle Problem Language Result Execution time Memory
957144 2024-04-03T05:11:55 Z Jawad_Akbar_JJ Cities (BOI16_cities) C++17
51 / 100
 4452 ms 50056 KB 
#pragma GCC optimize("O2")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include <iostream>
#include <vector>
#include <set>
 
using namespace std;
#define int long long
const int N = 1.1e5;
 
vector<pair<int,int>> nei[N];
int dp[N][33];
int sp[10],n,m,k;
 
void dijkstra(int ind){
	for (int i=1;i<N;i++)
		dp[i][1<<ind] = 1e17;
	dp[sp[ind]][1<<ind] = 0;
	
	set<pair<int,int>> st;
	st.insert({0,sp[ind]});
 
	while (st.size() > 0){
		int u = (*begin(st)).second;
		st.erase(begin(st));
 
		for (auto [i,c] : nei[u]){
			if (dp[i][1<<ind] > dp[u][1<<ind] + c){
				dp[i][1<<ind] = dp[u][1<<ind] + c;
				st.insert({dp[i][1<<ind],i});
			}
		}
	}
}
 
void calc(int msk){
	for (int smsk = 0;smsk <= msk;smsk ++){
		if ((msk | smsk) != msk)
			continue;
		for (int u=1;u<=n;u++){
			dp[u][msk] = min(dp[u][msk],dp[u][msk - smsk] + dp[u][smsk]);
			for (auto [i,c] :  nei[u]){
				dp[u][msk] = min(dp[u][msk],dp[u][smsk] + dp[i][msk - smsk] + c);
				dp[u][msk] = min(dp[u][msk],dp[i][smsk] + dp[i][msk - smsk] + c);
			}
		}
	}
}
 
 
signed  main(){
	// ios_base::sync_with_stdio(false);
	// cin.tie(NULL);
	// cout.tie(NULL);
	
	cin>>n>>k>>m;
 
	for (int i=1;i<=k;i++)
		cin>>sp[i-1];
 
	for (int i=1;i<=m;i++){
		int a,b,c;
		cin>>a>>b>>c;
		nei[a].push_back({b,c});
		nei[b].push_back({a,c});
	}
	
	for (int i=1;i<=n;i++)
		for (int j=1;j<32;j++)
			dp[i][j] = 1e17;
			
	for (int i=1;i<=k;i++)
		dijkstra(i-1);
	
	
	for (int i=0;i<32;i++){
		if (__builtin_popcount(i) == 2)
			calc(i);
	}
	
	for (int i=0;i<32;i++){
		if (__builtin_popcount(i) == 3)
			calc(i);
	}
	
	for (int i=0;i<32;i++){
		if (__builtin_popcount(i) == 4)
			calc(i);
	}
	
	for (int i=0;i<32;i++){
		if (__builtin_popcount(i) == 5)
			calc(i);
	}
	
	int Ans = 1e17;
	
	for (int i=1;i<=n;i++)
		Ans = min(Ans,dp[i][(1<<k) - 1]);
	cout<<Ans<<endl;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 31320 KB Output is correct
2 Correct 5 ms 31324 KB Output is correct
3 Correct 5 ms 31324 KB Output is correct
4 Correct 7 ms 31208 KB Output is correct
5 Correct 6 ms 31212 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4295 ms 49092 KB Output is correct
2 Correct 3776 ms 50056 KB Output is correct
3 Correct 2426 ms 38740 KB Output is correct
4 Correct 403 ms 43604 KB Output is correct
5 Correct 4235 ms 49092 KB Output is correct
6 Correct 409 ms 43684 KB Output is correct
7 Correct 11 ms 31580 KB Output is correct
8 Correct 10 ms 31576 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 31580 KB Output is correct
2 Correct 11 ms 31580 KB Output is correct
3 Correct 9 ms 31324 KB Output is correct
4 Correct 10 ms 31580 KB Output is correct

Subtask #4
0 / 23.0

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

Subtask #5
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4452 ms 49092 KB Output is correct
2 Incorrect 4439 ms 49076 KB Output isn't correct
3 Halted 0 ms 0 KB -