oj.uz

Submission #1103567

# Submission time Handle Problem Language Result Execution time Memory
1103567 2024-10-21T09:52:31 Z wayzzjr Cities (BOI16_cities) C++17
100 / 100
 3863 ms 58544 KB 
// ----------------------- 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

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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6736 KB Output is correct
2 Correct 2 ms 6736 KB Output is correct
3 Correct 2 ms 8784 KB Output is correct
4 Correct 3 ms 14984 KB Output is correct
5 Correct 4 ms 27272 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1596 ms 51880 KB Output is correct
2 Correct 790 ms 34804 KB Output is correct
3 Correct 657 ms 21944 KB Output is correct
4 Correct 61 ms 21420 KB Output is correct
5 Correct 1109 ms 47792 KB Output is correct
6 Correct 59 ms 19476 KB Output is correct
7 Correct 7 ms 9040 KB Output is correct
8 Correct 4 ms 6992 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 15184 KB Output is correct
2 Correct 9 ms 15184 KB Output is correct
3 Correct 6 ms 14928 KB Output is correct
4 Correct 9 ms 15184 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2598 ms 46256 KB Output is correct
2 Correct 1184 ms 38688 KB Output is correct
3 Correct 1114 ms 28048 KB Output is correct
4 Correct 1139 ms 44716 KB Output is correct
5 Correct 176 ms 31620 KB Output is correct
6 Correct 65 ms 30056 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3688 ms 57092 KB Output is correct
2 Correct 3863 ms 58544 KB Output is correct
3 Correct 2420 ms 48948 KB Output is correct
4 Correct 2894 ms 38876 KB Output is correct
5 Correct 2092 ms 56916 KB Output is correct
6 Correct 358 ms 43336 KB Output is correct
7 Correct 81 ms 42168 KB Output is correct