oj.uz

Submission #117155

# Submission time Handle Problem Language Result Execution time Memory
117155 2019-06-15T03:54:40 Z Just_Solve_The_Problem Cities (BOI16_cities) C++11
100 / 100
 4663 ms 57428 KB 
#include <bits/stdc++.h>

#define ll long long
#define ok puts("ok");

using namespace std;

const int N = (int)1e5 + 7;
const ll linf = (ll)1e18 + 7;

int n, k, m;
vector <pair<int, int>> gr[N];
vector <int> sp;
ll ans = 1e18;

map <pair<int, int>, int> mp;

ll dp[N][1 << 5];

main() {
	for (int i = 0; i < 32; i++) {
		for (int j = 0; j < N; j++) {
			dp[j][i] = linf;
		}
	}
	scanf("%d %d %d", &n, &k, &m);
	for (int i = 1, x; i <= k; i++) {
		scanf("%d", &x);
		sp.push_back(x);
		dp[x][1 << (i - 1)] = 0;
	}
	for (int i = 1, u, v, w; i <= m; i++) {
		scanf("%d %d %d", &u, &v, &w);
		if (u == v) continue;
		if (u > v) swap(u, v);
		if (!mp.count({u, v})) mp[{u, v}] = w;
		else mp[{u, v}] = min(w, mp[{u, v}]);
	}
	for (auto to : mp) {
		int u, v, w;
		u = to.first.first;
		v = to.first.second;
		w = to.second;
		gr[u].push_back({v, w});
		gr[v].push_back({u, w});
	}
	
	for (int mask = 1; mask < (1 << k); mask++) {
		int nx = mask;
		while (nx) {
			nx = (nx - 1) & mask;
			if (nx == 0) break;
			for (int i = 1; i <= n; i++) {
				dp[i][mask] = min(dp[i][mask], dp[i][mask ^ nx] + dp[i][nx]);
			}
		} 
		priority_queue <pair<ll, int>> q;
		for (int i = 1; i <= n; i++) {
			q.push({-dp[i][mask], i});
		}
		while (!q.empty()) {
			ll cur = -q.top().first;
			int v = q.top().second;
			q.pop();
			if (cur > dp[v][mask]) continue;
			for (auto id : gr[v]) {
				int to = id.first;
				int w = id.second;
				if (cur + w < dp[to][mask]) {
					dp[to][mask] = cur + w;
					q.push({-dp[to][mask], to});
				}
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		ans = min(ans, dp[i][(1 << k) - 1]);
	}
	cout << ans << endl;
}

Compilation message

cities.cpp:20:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main() {
      ^
cities.cpp: In function 'int main()':
cities.cpp:26:7: 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:28:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &x);
   ~~~~~^~~~~~~~~~
cities.cpp:33:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 27776 KB Output is correct
2 Correct 72 ms 27768 KB Output is correct
3 Correct 78 ms 27896 KB Output is correct
4 Correct 67 ms 27768 KB Output is correct
5 Correct 71 ms 27640 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1334 ms 57340 KB Output is correct
2 Correct 1322 ms 57372 KB Output is correct
3 Correct 819 ms 43120 KB Output is correct
4 Correct 442 ms 48516 KB Output is correct
5 Correct 828 ms 57348 KB Output is correct
6 Correct 418 ms 48540 KB Output is correct
7 Correct 73 ms 28024 KB Output is correct
8 Correct 68 ms 28024 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 28024 KB Output is correct
2 Correct 70 ms 27996 KB Output is correct
3 Correct 73 ms 27896 KB Output is correct
4 Correct 79 ms 28012 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2238 ms 57356 KB Output is correct
2 Correct 2512 ms 57428 KB Output is correct
3 Correct 1694 ms 43036 KB Output is correct
4 Correct 1495 ms 54036 KB Output is correct
5 Correct 565 ms 50672 KB Output is correct
6 Correct 423 ms 50168 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4663 ms 57288 KB Output is correct
2 Correct 4552 ms 57428 KB Output is correct
3 Correct 4450 ms 57360 KB Output is correct
4 Correct 3427 ms 43156 KB Output is correct
5 Correct 2438 ms 53916 KB Output is correct
6 Correct 720 ms 50420 KB Output is correct
7 Correct 523 ms 50012 KB Output is correct