oj.uz

Submission #535492

# Submission time Handle Problem Language Result Execution time Memory
535492 2022-03-10T11:34:36 Z ngpin04 Cities (BOI16_cities) C++14
100 / 100
 1935 ms 44652 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end() 
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
	if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
	if (a < b) {a = b; return true;} return false;
}
const int N = 1e5 + 5; 
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);

vector <pair <int, int>> adj[N];

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

int ct[N];
int n,m,k;

int bit(int x) {
	return (1 << x);
}

void solve(int mask) {
	for (int i = 1; i <= n; i++)
	for (int s = mask; s > 0; s = (s - 1) & mask) 
		mini(dp[mask][i], dp[s][i] + dp[mask ^ s][i]);
	
	priority_queue <pair <long long, int>> heap;

	for (int i = 1; i <= n; i++)
		if (dp[mask][i] < ooo)
			heap.push(mp(-dp[mask][i], i));

	while (heap.size()) {
		int u = heap.top().se;
		long long cur = -heap.top().fi;
		heap.pop();
		if (cur != dp[mask][u])
			continue;

		for (pair <int, int> to : adj[u]) {
			int v = to.fi;
			int w = to.se;
			if (mini(dp[mask][v], dp[mask][u] + w))
				heap.push(mp(-dp[mask][v], v));
		}	
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	#ifdef ONLINE_JUDGE
	// freopen(TASK".inp","r",stdin);
	// freopen(TASK".out","w",stdout);
	#endif
	scanf("%d%d%d", &n, &k, &m);
	for (int i = 1; i <= k; i++)
		scanf("%d", &ct[i]);

	for (int i = 1; i <= m; i++) {
		int u,v,w;
		scanf("%d%d%d", &u, &v, &w);
		adj[u].push_back(mp(v, w));
		adj[v].push_back(mp(u, w));
	}

	for (int mask = 0; mask < bit(k); mask++)
	for (int i = 1; i <= n; i++)
		dp[mask][i] = ooo;


	for (int i = 1; i <= k; i++)
		dp[bit(i - 1)][ct[i]] = 0;
	
	for (int mask = 0; mask < bit(k); mask++)
		solve(mask);

	long long ans = ooo;
	for (int i = 1; i <= n; i++)
		mini(ans, dp[bit(k) - 1][i]);

	printf("%ld", ans);
	return 0;
}

Compilation message

cities.cpp: In function 'int main()':
cities.cpp:91:12: warning: format '%ld' expects argument of type 'long int', but argument 2 has type 'long long int' [-Wformat=]
   91 |  printf("%ld", ans);
      |          ~~^   ~~~
      |            |   |
      |            |   long long int
      |            long int
      |          %lld
cities.cpp:65:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |  scanf("%d%d%d", &n, &k, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
cities.cpp:67:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |   scanf("%d", &ct[i]);
      |   ~~~~~^~~~~~~~~~~~~~
cities.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d%d%d", &u, &v, &w);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
22.0 / 22.0

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

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 499 ms 25840 KB Output is correct
2 Correct 436 ms 25864 KB Output is correct
3 Correct 325 ms 17804 KB Output is correct
4 Correct 58 ms 10876 KB Output is correct
5 Correct 237 ms 20532 KB Output is correct
6 Correct 83 ms 10828 KB Output is correct
7 Correct 4 ms 2864 KB Output is correct
8 Correct 3 ms 2820 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2952 KB Output is correct
2 Correct 6 ms 3004 KB Output is correct
3 Correct 5 ms 2972 KB Output is correct
4 Correct 4 ms 2900 KB Output is correct

Subtask #4
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 968 ms 32120 KB Output is correct
2 Correct 926 ms 32068 KB Output is correct
3 Correct 658 ms 24180 KB Output is correct
4 Correct 518 ms 22556 KB Output is correct
5 Correct 136 ms 13536 KB Output is correct
6 Correct 66 ms 12620 KB Output is correct

Subtask #5
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1935 ms 44636 KB Output is correct
2 Correct 1813 ms 44652 KB Output is correct
3 Correct 1752 ms 44584 KB Output is correct
4 Correct 1193 ms 36892 KB Output is correct
5 Correct 942 ms 28948 KB Output is correct
6 Correct 214 ms 14900 KB Output is correct
7 Correct 75 ms 12720 KB Output is correct