Submission #1103565

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1103565	2024-10-21T09:51:46 Z	wayzzjr	Cities (BOI16_cities)	C++17	Compilation error	0 ms	0 KB

cities

// ----------------------- TEMPLATE NO.4 ---------------------------
#ifndef ONLINE_JUDGE
#include "D:\File cua Wayzz\DSA\Debug Template\template.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll, ll> 
const ll mod = 1e9 + 7;
const int N = 1e5 + 100;
const ll oo = 1e16;

// loops
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define ROF(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)

// others :>
#define nl '\n'
//----------------------------------SOLUTION-----------------------------------//

int n, m, k;
ll dp[1<<5][N];
vector<ii> adj[N];

bool minimize(ll& a, ll b){
	if(a > b) {a = b; return 1;}
	return 0;
}

void solve(){
	cin >> n >> k >> m;
	vector<int> cities(k);
	for(int &v : cities) cin >> v;

	FOR(i, 1, m){
		int u, v, w; cin >> u >> v >> w;
		adj[u].push_back({v, w});
		adj[v].push_back({u, w});
	}

	FOR(mask, 1, (1 << k) - 1) FOR(i, 1, n){
		dp[mask][i] = oo;
	}
	FOR(i, 0, k-1) dp[1<<i][cities[i]] = 0;

	FOR(mask, 1, (1 << k) - 1){
		for(int submask = (mask - 1) & mask; submask > 0; submask = (submask - 1) & mask){
			FOR(i, 1, n) minimize(dp[mask][i], dp[submask][i] + dp[mask - submask][i]);
		}

		priority_queue<ii, vector<ii>, greater<ii>> pq;
		FOR(i, 1, n) if(dp[mask][i] != oo){
			pq.push({i, dp[mask][i]});
		}

		while(!pq.empty()){
			auto [u, dist] = pq.top();
			pq.pop();

			if(dist > dp[mask][u]) continue;
			for(auto [v, w] : adj[u]){
				if(minimize(dp[mask][v], dp[mask][u] + w)){
					pq.push({v, dp[mask][v]});
				}
			}
		}
	}

	ll res = oo;
	FOR(i, 1, n) minimize(res, dp[(1<<k)-1][i]);
	cout << res;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	#define Wayzz "name"
	if (fopen (Wayzz".inp", "r")) {
		freopen (Wayzz".inp", "r", stdin);
		freopen (Wayzz".out", "w", stdout);
	}
	int T = 1;
    while(T--) solve();
	cerr <<"\nTime Elapse: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

Compilation message

cities.cpp:3:10: fatal error: D:\File cua Wayzz\DSA\Debug Template\template.cpp: No such file or directory
    3 | #include "D:\File cua Wayzz\DSA\Debug Template\template.cpp"
      |          ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
compilation terminated.