fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define piint pair < int , int >
  4. #define ALL(a) (a).begin() , (a).end
  5. using namespace std;
  6. const int maxn = 301 ;
  7. int p[maxn+3][maxn + 3 ] ;
  8. ll W = 0 ;
  9. int n ;
  10. bool water[maxn+3] ;
  11. ll d[maxn + 3 ] ;
  12. int w[maxn+3] ;
  13. #define debug 0
  14. ll PRIM ( int s ) {
  15.     // truong hop di tu s dau tien
  16.     // duyet moi dinh oke ?
  17.     // voi dinh nay ta tim duong di nho nhat
  18.     // noi voi dinh do
  19.     // neu ma dinh do xet roi , ta xem val cua duong di dinh do co be hon dat tai no khong
  20.     // neu co thi chu di
  21.     // con neu khong thi ta du nguyen ?
  22.     for (int i = 1 ; i <= n ; i ++ ){
  23.         d[i] = 1e17 ;
  24.         water[i] = 0 ;
  25.     }
  26.     d[s] = w[s] ; W = 0;
  27.     priority_queue < piint , vector < piint > ,greater < piint > > q ;
  28.     q.push({ d[s] , s }) ;
  29.     while (q.size()){
  30.         auto [du,u] = q.top() ; q.pop() ;
  31.         if (d[u] != du ) continue ;
  32.         if (water[u]) continue ;
  33.          W += d[u] ;
  34.         //else W += w[u] ;
  35.         if ( debug ){
  36.                 cout << "U = : " << ' ' << u << '\n';
  37.             cout << "W = " << W << ": du" << ' ' << du <<" : w[u]  " << w[u] << '\n' ;
  38.         }
  39.         d[u] = -1e17 ;
  40.         water[u] = 1 ;
  41.         for (int j =  1 ; j <= n ; j ++ ){
  42.             ll val = p[u][j] ;
  43.                 if (d[j] > w[j] && w[j] != val ){
  44.                 d[j] = w[j] ;
  45.                 q.push( { d[j] , j }) ;
  46.                 }
  47.                 if (d[j] > val && w[j] != val  && u != j ){
  48.                     d[j] = val ;
  49.                     q.push( { d[j] , j }) ;
  50.             }
  51.         }
  52.     }
  53.     return W ;
  54. }
  55. void sovle(){
  56.     cin >> n ;
  57.     for (int i = 1 ; i <= n ; i ++ ) {
  58.         cin >> w[i] ;
  59.     }
  60.     for (int i = 1 ; i <= n ; i ++ ){
  61.         for (int j = 1 ; j <= n ; j ++ ) cin >> p[i][j] ;
  62.     }
  63.     ll res = 1e17 ;
  64.     for (int i = 1 ; i <= n ; i ++ ){
  65.     res = min ( res , PRIM(i)) ;
  66.         cerr << "end\n" ;
  67.     }
  68.     cout << W ;
  69. }
  70. int main()
  71. {
  72.     ios_base::sync_with_stdio(0) ;
  73.     cin.tie(0); cout.tie(0) ;
  74.     int q = 1 ;
  75.     // cin >> q ;
  76.     while ( q -- ) sovle() ;
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/7Yrws7
language:
C++14 (gcc 8.3)
created:
11 days 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!