oj.uz

Submission #866205

# Submission time Handle Problem Language Result Execution time Memory
866205 2023-10-25T15:24:38 Z alwaystle Cities (BOI16_cities) C++17
100 / 100
 1772 ms 47924 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define file "test"
#define vi vector
#define sz(_v) _v.begin(), _v.end()
#define mask(_x) (1ll << (_x))
#define mp make_pair
#define fi first
#define se second
typedef pair<ll,int> pa;
 
const ll inf = ll(1e16) + 1;
const int N = 1e5 + 5;
int n, m, k, x, y, i, a[6], j, l, p;
vi<pa> adj[N];
ll z, dp[1 << 5][N], o = inf;
bool dd[N];
priority_queue<pa> pq;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	#ifdef umf
	freopen(file".inp","r",stdin); freopen(file".out","w",stdout);
	// freopen("debug.txt","w",stderr);
	#endif
 
	cin >> n >> k >> m;
	for(i = 1; i <= k; ++i) cin >> a[i];
	while(m--) {
		cin >> x >> y >> z;
		adj[x].push_back(mp(z,y));
		adj[y].push_back(mp(z,x));
	}
	memset(dp,63,sizeof(dp));
	for(i = 0; i < k; ++i) dp[mask(i)][a[i + 1]] = 0;
	for(i = 1; i < mask(k); ++i) {
		for(j = 0; j < i; ++j)
			if((i | j) == i) {
				l = i ^ j;
				if(l < j) for(p = 1; p <= n; ++p) dp[i][p] = min(dp[i][p],dp[j][p] + dp[l][p]);
			}
		memset(dd,false,sizeof(dd));
		for(j = 1; j <= n; ++j)
			if(dp[i][j] < inf) pq.push(mp(-dp[i][j],j));
		while(!pq.empty()) {
			x = pq.top().se;
			pq.pop();
			dd[x] = true;
			for(j = 0; j < adj[x].size(); ++j) {
				y = adj[x][j].se;
				z = adj[x][j].fi;
				if(!dd[y] && dp[i][x] + z < dp[i][y]) {
					dp[i][y] = dp[i][x] + z;
					pq.push(mp(-dp[i][y],y));
				}
			}
			while(!pq.empty() && dd[pq.top().se]) pq.pop();
		}
	}
	x = mask(k) - 1;
	for(i = 1; i <= n; ++i) o = min(o,dp[x][i]);
	cout << o;
 
	return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:50:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |    for(j = 0; j < adj[x].size(); ++j) {
      |               ~~^~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 390 ms 47844 KB Output is correct
2 Correct 348 ms 46628 KB Output is correct
3 Correct 241 ms 37292 KB Output is correct
4 Correct 68 ms 40276 KB Output is correct
5 Correct 186 ms 47556 KB Output is correct
6 Correct 63 ms 40556 KB Output is correct
7 Correct 7 ms 28164 KB Output is correct
8 Correct 5 ms 28000 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 27996 KB Output is correct
2 Correct 8 ms 27948 KB Output is correct
3 Correct 6 ms 27996 KB Output is correct
4 Correct 7 ms 27996 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 816 ms 47924 KB Output is correct
2 Correct 769 ms 46904 KB Output is correct
3 Correct 490 ms 37284 KB Output is correct
4 Correct 447 ms 44696 KB Output is correct
5 Correct 142 ms 41144 KB Output is correct
6 Correct 94 ms 42384 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1707 ms 46788 KB Output is correct
2 Correct 1772 ms 47292 KB Output is correct
3 Correct 1528 ms 46904 KB Output is correct
4 Correct 1055 ms 37320 KB Output is correct
5 Correct 868 ms 45036 KB Output is correct
6 Correct 226 ms 41440 KB Output is correct
7 Correct 124 ms 42820 KB Output is correct