oj.uz

Submission #132657

# Submission time Handle Problem Language Result Execution time Memory
132657 2019-07-19T09:41:54 Z arman_ferdous Cities (BOI16_cities) C++17
100 / 100
 3217 ms 46696 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<ll,int>;
const int N = 1e5+100;
const int M = 2e5+100;
const ll oo = 1e18;

int n, k, m, sp[5];
ll dp[40][N];
vector<ii> g[N];
priority_queue<ii,vector<ii>,greater<ii>> q;

int main() {
	scanf("%d %d %d", &n, &k, &m);
	for(int i = 0; i < k; i++)
		scanf("%d", &sp[i]);
	for(int i = 0; i < m; i++) {
		int u, v; ll w;
		scanf("%d %d %lld", &u, &v, &w);
		g[u].push_back({w, v});
		g[v].push_back({w, u});
	}
	for(int i = 0; i < (1 << k); i++)
		for(int j = 1; j <= n; j++)
			dp[i][j] = oo;
	for(int i = 0; i < k; i++)
		dp[(1 << i)][sp[i]] = 0;

	for(int mask = 1; mask < (1 << k); mask++) {
		for(int c = 0; c < mask; c++) {
			if((mask & c) == c) {
				for(int i = 1; i <= n; i++) 
					dp[mask][i] = min(dp[mask][i], dp[c][i] + dp[(c ^ mask)][i]);
			}
		}
		for(int i = 1; i <= n; i++) if(dp[mask][i] < oo) 
			q.push({dp[mask][i], i});
		while(!q.empty()) {
			int u = q.top().second;
			ll cw = q.top().first; q.pop();
			for(auto e : g[u]) {
				int v = e.second; ll w = e.first;
				if(dp[mask][v] > cw + w) {
					dp[mask][v] = cw + w;
					q.push({dp[mask][v], v});
				}
			}
		}
	}
	ll ans = oo;
	for(int i = 1; i <= n; i++)
		ans = min(ans, dp[(1 << k) - 1][i]);
	printf("%lld\n", ans);
	return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:16: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:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &sp[i]);
   ~~~~~^~~~~~~~~~~~~~
cities.cpp:21:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld", &u, &v, &w);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2684 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2808 KB Output is correct
5 Correct 4 ms 2936 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 825 ms 27848 KB Output is correct
2 Correct 881 ms 26980 KB Output is correct
3 Correct 451 ms 18540 KB Output is correct
4 Correct 123 ms 15352 KB Output is correct
5 Correct 406 ms 24696 KB Output is correct
6 Correct 115 ms 15224 KB Output is correct
7 Correct 8 ms 2936 KB Output is correct
8 Correct 6 ms 2936 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 3064 KB Output is correct
2 Correct 10 ms 3064 KB Output is correct
3 Correct 8 ms 2940 KB Output is correct
4 Correct 8 ms 2936 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1560 ms 33988 KB Output is correct
2 Correct 1522 ms 33140 KB Output is correct
3 Correct 1020 ms 24812 KB Output is correct
4 Correct 913 ms 25808 KB Output is correct
5 Correct 330 ms 17372 KB Output is correct
6 Correct 136 ms 17360 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3164 ms 46572 KB Output is correct
2 Correct 3217 ms 46696 KB Output is correct
3 Correct 3147 ms 45664 KB Output is correct
4 Correct 2263 ms 37284 KB Output is correct
5 Correct 1860 ms 32092 KB Output is correct
6 Correct 409 ms 18900 KB Output is correct
7 Correct 158 ms 17492 KB Output is correct