Submission #1286563

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286563		behesht	Cities (BOI16_cities)	C++20	37 / 100	6094 ms	78280 KiB

cities

#include <bits/stdc++.h>

#define d1(x)                cout << #x << " : " << x << endl << flush
#define d2(x, y)             cout << #x << " : " << x << "   " << #y << " : " << y << endl << flush
#define d3(x, y, z)          cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << endl << flush
#define d4(x, y, z, a)       cout << #x << " : " << x << "   " << #y << " : " << y << "   " << #z << " : " << z << "    "<< #a << " : " << a << endl << flush
#define arr(x)               array <ll, x>
#define ld                   long double
#define ll                   long long
#define int                  long long
#define pb                   push_back
#define endl                 '\n'
#define lc                   v << 1
#define rc                   v << 1 | 1

using namespace std;

const int INF = 1e12 + (35 / 10); // 35 ---> 36
const int MAXN = 2e5 + (35 / 10); // 35 ---> 36
const int LOG = 35;

int mini[MAXN][LOG], c[MAXN];
int dp[MAXN][LOG];
vector <int> f[MAXN];
vector <arr(2)> adj[MAXN];

// void get(int x){
// 	for(int i = 3; i >= 0; i--)
// 		cout << ((x >> i) & 1);
// 	cout << ' ';
// }

signed main(){
	
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	int n, k, m;
	cin >> n >> k >> m;

	for(int msk = 1; msk < (1ll << k); msk++)
		for(int msk2 = 1; msk2 < (1ll << k); msk2++)
			if((msk & msk2) == msk2 && msk != msk2)
				f[msk].pb(msk2);

	for(int i = 0; i < k; i++){
		cin >> c[i];
		c[i]--;
	}

	for(int i = 0; i < m; i++){
		int u, v, w;
		cin >> u >> v >> w;

		u--;
		v--;

		adj[u].pb({v, w});
		adj[v].pb({u, w});
	}

	for(int msk = 1; msk < (1ll << k); msk++){
		
		for(int i = 0; i < n; i++)
			dp[i][msk] = mini[i][msk] = INF;
		
		if(__builtin_popcount(msk) == 1){
			for(int i = 0; i < k; i++){
				if((msk >> i) & 1){
					dp[c[i]][msk] = 0;	
				}
			}
		}

		set <arr(2)> s;
		// d2("------", msk);

		for(int i = 0; i < n; i++){
			// d1(i);

			for(auto a : f[msk]){
				int b = msk ^ a;
				dp[i][msk] = min(dp[i][msk], dp[i][a] + mini[i][b]);
				// get(a);
				// get(b);
				// d2(dp[i][a], mini[i][b]);
			}

			// d2(i, dp[i][msk]);
			s.insert({dp[i][msk], i});
		}

		// dijkstraaaaa

		while(!s.empty()){
			auto [_, u] = *s.begin();
			s.erase(*s.begin());

			for(auto [v, w] : adj[u]){
				if(dp[v][msk] > dp[u][msk] + w){
					dp[v][msk] = dp[u][msk] + w;
					s.insert({dp[v][msk], v});
				}
			}
		}

		for(int i = 0; i < n; i++)
			for(auto [v, w] : adj[i])
				mini[v][msk] = min(mini[v][msk], dp[i][msk] + w);

		// cout << endl;
	}

	int mn = INF;

	for(int i = 0; i < n; i++)
		mn = min(mn, dp[i][(1ll << k) - 1]);

	cout << mn << endl;
}

// Ey To Bahane! :_)))

// -------------<3------------- //
/*
Magasan dor shirini: 

1. MAXN
2. Input style
3. index or value? Masale In Ast!	
4. MOD 

*/

/*
8 2 8
1 8
1 2 1
2 3 2
3 4 4
4 5 8
5 6 16
6 7 32 
7 8 64
1 8 254
*/

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