Submission #1103567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1103567		wayzzjr	Cities (BOI16_cities)	C++17	100 / 100	3863 ms	58544 KiB

cities

// ----------------------- TEMPLATE NO.4 ---------------------------
#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 (stderr)

cities.cpp: In function 'int main()':
cities.cpp:76:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   76 |   freopen (Wayzz".inp", "r", stdin);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
cities.cpp:77:11: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |   freopen (Wayzz".out", "w", stdout);
      |   ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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