fork download
  1. /**
  2.  * author: orzvanh14 ( )
  3.  * created: 23.12.2022 10:08:02
  4.  * too lazy to update time
  5. **/
  6. // i wants to take ioi
  7. //binhtinhtutinkhongcaycunhungmotkhikhongcontutinnualatuyetvong
  8. #include <bits/stdc++.h>
  9.  
  10. using namespace std;
  11.  
  12. #define int long long
  13. #define nn "\n"
  14. #define pi pair<int, int>
  15. #define fi first
  16. #define se second
  17. #define lb lower_bound
  18. #define ub upper_bound
  19. #define eb emplace_back
  20. #define pb push_back
  21. #define TASK " "
  22.  
  23. #define ms(a, x) memset(a, x, sizeof(a))
  24. #define all(a) a.begin(), a.end()
  25. #define All(a, n) a + 1, a + 1 + n
  26.  
  27. #define LOG 19
  28.  
  29.  
  30. const int INF = 1e18;
  31. const int mod = 1e9+7;
  32. const int N = 5e2 + 5;
  33. int MOD = 998244353;
  34. int bit[200000];
  35. struct node{
  36. int kc, u, hk;
  37. bool operator<(const node& other) const {
  38. return kc > other.kc;
  39. }
  40. };
  41. struct edge{
  42. int u, v, w;
  43. friend bool operator < ( edge a, edge b){
  44. return a.w < b.w;
  45. }
  46. };
  47. vector<edge> adj;
  48. int n;
  49. int lab[N];
  50. int a[N], b[N][N];
  51. int get(int v){
  52. if(lab[v] < 0) return v;
  53. return lab[v] = get(lab[v]);
  54. }
  55. bool union_sets(int a, int b){
  56. a = get(a);
  57. b = get(b);
  58. if(a != b){
  59. if(lab[a] > lab[b]) swap(a, b);
  60. lab[a] += lab[b];
  61. lab[b] = a;
  62. return true;
  63. }
  64. else return false;
  65.  
  66. }
  67. void nhap(){
  68. cin >> n;
  69. for(int i = 1; i <= n; i++){
  70. cin >> a[i];
  71. adj.push_back({0, i, a[i]});
  72. }
  73. for(int i = 1; i <= n;i++){
  74. for(int j = 1; j <= n ; j++){
  75. cin >> b[i][j];
  76. }
  77. }
  78. for(int i = 1; i <= n; i++){
  79. for(int j = i + 1; j <= n; j++){
  80. adj.push_back({i, j, b[i][j]});
  81. }
  82. }
  83. }
  84. void solve(){
  85. memset(lab, -1, sizeof(lab));
  86. sort(adj.begin(), adj.end());
  87. int ans = 0;
  88. for(auto edges : adj){
  89. if(union_sets( edges.u, edges.v ) ) ans += edges.w;
  90. }
  91. cout << ans << nn;
  92. }
  93. signed main() {
  94. // freopen("piggyback.in", "r", stdin);
  95. // freopen("piggyback.out", "w", stdout);
  96. ios_base::sync_with_stdio(0);
  97. cin.tie(0);
  98. cout.tie(0);
  99. nhap();
  100. solve();
  101. return 0;
  102.  
  103. }
Success #stdin #stdout 0s 5732KB
stdin
Standard input is empty
stdout
0