fork download
copy 
  1. #include <cstdio>
  2. #include <vector>
  3. #include <algorithm>
  4. using namespace std;
  5. typedef long long ll;
  6. #define MN 55
  7. const ll inf = 999999999999999999LL;
  8. int n, before[MN], after[MN], houseCost[MN], roadCost, diff[MN];
  9. ll D[MN][MN], res, d[MN];
  10. char chk[MN], g[MN][MN];
  11. inline ll f(int u, int v) {
  12. 	ll v1 = (ll)(before[u]) * diff[v] * houseCost[v] + (ll)(after[v]) * diff[u] * houseCost[u];
  13. 	ll v2 = (ll)(before[v]) * diff[u] * houseCost[u] + (ll)(after[u]) * diff[v] * houseCost[v];
  14. 	return min(v1, v2);
  15. }
  16. void prim(int v) {
  17. 	res += d[v];
  18. 	chk[v] = 1;
  19. 	int i, bi = -1;
  20. 	ll mincost = inf;
  21. 	for (i = 0; i < n; i++) {
  22. 		if (D[v][i] < d[i]) {
  23. 			d[i] = D[v][i];
  24. 		}
  25. 		if (!chk[i] && d[i] < mincost) {
  26. 			mincost = d[i];
  27. 			bi = i;
  28. 		}
  29. 	}
  30. 	if (bi >= 0) prim(bi);
  31. }
  32. int main() {
  33. 	scanf("%d", &n);
  34. 	for (int i = 0; i < n; i++) scanf("%d", &before[i]);
  35. 	for (int i = 0; i < n; i++) scanf("%d", &after[i]);
  36. 	for (int i = 0; i < n; i++) scanf("%d", &houseCost[i]);
  37. 	for (int i = 0; i < n; i++) scanf("%s", g[i]);
  38. 	scanf("%d", &roadCost);
  39. 	for (int i = 0; i < n; i++) {
  40. 		diff[i] = after[i] - before[i];
  41. 		res += ((long long)(diff[i]) * (before[i] + after[i] - 1) / 2) * houseCost[i];
  42. 		d[i] = inf;
  43. 	}
  44. 	for (int i = 0; i < n; i++) {
  45. 		for (int j = i + 1; j < n; j++) {
  46. 			if (g[i][j] == 'Y') D[i][j] = 0, res += f(i, j);
  47. 			else D[i][j] = (before[i] + before[j]) * (long long)(roadCost)+f(i, j);
  48. 			D[j][i] = D[i][j];
  49. 		}
  50. 	}
  51. 	d[0] = 0;
  52. 	prim(0);
  53. 	printf("%lld", res);
  54. }
Success #stdin #stdout 0s 3328KB
comments (?)
stdin
copy 
4
2 1 3 5
2 1 3 5
4 5 3 2
NNNN
NNNN
NNNN
NNNN
1000
stdout
copy 
13000
https://ideone.com/KY3dAf
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!