oj.uz

Submission #1010366

# Submission time Handle Problem Language Result Execution time Memory
1010366 2024-06-29T01:34:22 Z uyt777443 Cities (BOI16_cities) C++14
100 / 100
 1737 ms 50748 KB 
// https://oj.uz/problem/view/BOI16_cities

#include <iostream>
#include <iomanip>
#include <stack>
#include <queue>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <vector>
#include <utility>
#include <algorithm>
#include <numeric>
#include <string>
#include <cmath>
#include <random>
#include <sstream>
#include <string.h>
#include <assert.h>
#include <limits.h>
using namespace std;

#define fi first
#define se second
#define int long long
#define pb push_back

typedef pair<int,int> ii;

const int INF = 1e18;

vector<vector<ii> > adj(100000 + 2);
vector<int> sp;
int dp[100000 + 2][32 + 2];

signed main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, k, m; cin >> n >> k >> m;
	for (int i=1; i<=k; i++) {
		int a; cin >> a; sp.pb(a);
	}
	for (int i=1; i<=m; i++) {
		int a, b, c; cin >> a >> b >> c; adj[a].pb({b, c}); adj[b].pb({a, c});
	}

	for (int i=1; i<=n; i++) for (int j=0; j<=32; j++) dp[i][j] = INF;

	for (int i=0; i<k; i++) 
		dp[sp[i]][(1 << i)] = 0;
	// for (auto i : sp)
  
	for (int mask = 1; mask <= (1 << k) - 1; mask++) {
    	for (int i=0; i<5; i++) {
			if (mask & (1 << i)) {
				for (int j=1; j<=n; j++) 
					dp[j][mask] = min(dp[j][mask], dp[j][mask - (1 << i)] + dp[j][(1 << i)]);
			}
		}
		
		priority_queue<ii, vector<ii>, greater<ii> > pq;
		for (int i=1; i<=n; i++) {
			pq.push({dp[i][mask], i});
		}
		
		while(!pq.empty()) {
			ii cur = pq.top(); pq.pop();
			int des = cur.se, dis = cur.fi;
            if (dp[des][mask] != dis) continue; 
			for (auto nx : adj[des]) {
				int ndes = nx.fi, w = nx.se;
                int nxmask = mask;
				// for (int i=0; i<5; i++) {
				// 	if (ndes == sp[i]) nxmask += (1 << i);
				// }
				if (dp[ndes][nxmask] <= dp[des][mask] + w) continue;
                dp[ndes][nxmask] = dp[des][nxmask] + w;
                pq.push({dp[ndes][nxmask], ndes});
			}
		}
	}

	int ans = INF;
	for (int i=1; i<=n; i++) {
		ans = min(ans, dp[i][(1 << k) - 1]);
	} cout << ans;
	
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Correct 1 ms 2904 KB Output is correct
3 Correct 1 ms 2652 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 2652 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 481 ms 50356 KB Output is correct
2 Correct 399 ms 49884 KB Output is correct
3 Correct 233 ms 40380 KB Output is correct
4 Correct 41 ms 15516 KB Output is correct
5 Correct 247 ms 50504 KB Output is correct
6 Correct 34 ms 15440 KB Output is correct
7 Correct 3 ms 3164 KB Output is correct
8 Correct 2 ms 3164 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3160 KB Output is correct
2 Correct 5 ms 3164 KB Output is correct
3 Correct 3 ms 3416 KB Output is correct
4 Correct 3 ms 2908 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 806 ms 50476 KB Output is correct
2 Correct 804 ms 50032 KB Output is correct
3 Correct 563 ms 40624 KB Output is correct
4 Correct 390 ms 34536 KB Output is correct
5 Correct 104 ms 19824 KB Output is correct
6 Correct 41 ms 17704 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1679 ms 50748 KB Output is correct
2 Correct 1737 ms 50704 KB Output is correct
3 Correct 1595 ms 50036 KB Output is correct
4 Correct 1082 ms 40408 KB Output is correct
5 Correct 747 ms 34508 KB Output is correct
6 Correct 164 ms 19740 KB Output is correct
7 Correct 58 ms 17876 KB Output is correct