oj.uz

Submission #21003

# Submission time Handle Problem Language Result Execution time Memory
21003 2017-03-27T11:01:38 Z model_code Cities (BOI16_cities) C++11
100 / 100
 2733 ms 71636 KB 
#include <iostream>
#include <climits>
#include <queue>
#include <cstdio>

using namespace std;
typedef long long int Z;

int n, k, m;
vector<int> imp;
vector<vector<pair<int, Z>>> G;
Z d[32][202020];
Z huge = LLONG_MAX / 3;
bool seen[202020];

int main() {
	scanf("%d%d%d", &n, &k, &m);
	imp.resize(k);
	for(int i = 0; i < k; ++i) {
		scanf("%d", &imp[i]);
		--imp[i];
	}
	
	G.resize(n);
	for(int i = 0; i < m; ++i) {
		int a, b;
		Z c;
	      scanf("%d%d%lld", &a, &b, &c);
		--a;
		--b;
		G[a].emplace_back(b, c);
		G[b].emplace_back(a, c);
	}
	
	fill((Z*)d, (Z*)d + 32 * 202020, huge);
	
	for(int i = 0; i < k; ++i) {
		d[1 << i][imp[i]] = 0;
	}
	
	priority_queue<pair<Z, int>> Q;
	for(int c = 1; c < (1 << k); ++c) {
		for(int a = 0; a < c; ++a) {
			if((a | c) != c) continue;
			int b = c ^ a;
			if(b > a) continue;
			for(int v = 0; v < n; ++v) {
				d[c][v] = min(d[c][v], d[a][v] + d[b][v]);
			}
		}
		fill(seen, seen + n, false);
		for(int v = 0; v < n; ++v) {
			if(d[c][v] == huge) continue;
			Q.emplace(-d[c][v], v);
		}
		
		while(!Q.empty()) {
			Z cost = -Q.top().first;
			int v = Q.top().second;
			Q.pop();
			if(seen[v]) continue;
			seen[v] = true;
			for(auto edge : G[v]) {
				Z ec = cost + edge.second;
				if(ec < d[c][edge.first]) {
					d[c][edge.first] = ec;
					Q.emplace(-ec, edge.first);
				}
			}
		}
	}
	
	Z res = huge;
	for(int v = 0; v < n; ++v) {
		res = min(res, d[(1 << k) - 1][v]);
	}
	cout << res << '\n';
	
	return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:17:29: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &n, &k, &m);
                             ^
cities.cpp:20:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &imp[i]);
                       ^
cities.cpp:28:37: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
        scanf("%d%d%lld", &a, &b, &c);
                                     ^

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 52724 KB Output is correct
2 Correct 13 ms 52724 KB Output is correct
3 Correct 3 ms 52724 KB Output is correct
4 Correct 6 ms 52724 KB Output is correct
5 Correct 9 ms 52724 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 753 ms 71636 KB Output is correct
2 Correct 739 ms 71516 KB Output is correct
3 Correct 416 ms 63424 KB Output is correct
4 Correct 129 ms 61704 KB Output is correct
5 Correct 413 ms 71616 KB Output is correct
6 Correct 119 ms 61696 KB Output is correct
7 Correct 9 ms 53000 KB Output is correct
8 Correct 3 ms 53000 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 53000 KB Output is correct
2 Correct 13 ms 52988 KB Output is correct
3 Correct 16 ms 52856 KB Output is correct
4 Correct 9 ms 52856 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1459 ms 71636 KB Output is correct
2 Correct 1276 ms 71252 KB Output is correct
3 Correct 853 ms 63424 KB Output is correct
4 Correct 769 ms 67404 KB Output is correct
5 Correct 266 ms 64068 KB Output is correct
6 Correct 119 ms 64936 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2646 ms 71624 KB Output is correct
2 Correct 2733 ms 71608 KB Output is correct
3 Correct 2689 ms 71332 KB Output is correct
4 Correct 2009 ms 63428 KB Output is correct
5 Correct 1439 ms 67396 KB Output is correct
6 Correct 419 ms 64072 KB Output is correct
7 Correct 146 ms 65180 KB Output is correct