Language: C++







//****************************************
// 必要なヘッダファイルのインクルード
//****************************************

#include <functional>
#include <utility>
#include <algorithm>
#include <vector>
#include <cassert>
#include <tuple>
#include <queue>
#include <iostream>



//****************************************
// オブジェクト形式マクロの定義
//****************************************

#define GRAPH_BEGIN namespace graph {
#define GRAPH_END   }



//****************************************
// 名前空間の始端
//****************************************

GRAPH_BEGIN



//****************************************
// 構造体の定義
//****************************************

using weight_t   = std::int32_t;  /**< 辺(u, v)への重みwを表す型 */
using index_t    = std::int32_t;  /**< 頂点vの添字を表す型       */
using capacity_t = weight_t;      /**< 辺(u, v)の容量を表す型    */



namespace limits {
    enum {  // scopedではあるが強く型付けされたenum(strongly-typed enum)ではない
        inf = std::numeric_limits<weight_t>::max() / 3,  /**< @brief 辺が存在しない場合に使用される値     */
        nil = std::numeric_limits<index_t>::min() / 3,   /**< @brief 先行点が存在しない場合に使用される値 */
    };
}



/**
 * @brief  頂点色列挙構造体(scoped enum)
 * @detail (u, v) ∈ Eで頂点uが黒ならば頂点vは灰か黒である
 *         すなわち、黒頂点に隣接する全ての頂点は発見済みである
 *         灰頂点は白頂点に隣接することがあり、これらの頂点が既発見頂点と未発見頂点の境界をなす
 */
enum struct vcolor : std::int32_t {
    white,  /**< 未発見頂点 */
    black,  /**< 既発見頂点 */
    gray,   /**< 既見済頂点 */
};

/**
 * @brief グラフ用ノード(頂点) 
 */
struct vertex {
    union {
        weight_t d;       /**< 始点sからの距離  */
        weight_t key;     /**< Primのアルゴリズムにおいて木に属するある頂点とを結ぶ重み */
    };
    index_t pi;           /**< 先行頂点(の添字) */
    union {
        vcolor color;     /**< 頂点の色        */
        bool  visited;    /**< 発見済みか?     */
    };
    // weight_t f;           /**< 終了時刻印(DFSにおいて、黒色に彩色されたとき、刻まれる)     */
    vertex() : d(0), pi(0), color(vcolor::white)/*, f(0)*/ {}
};

/**
 * @brief グラフ用エッジ(辺)
 * @note  G = (V, E)を重み関数wを持つ重み付きグラフとすると、
 *        辺(u, v) ∈ Eの重みはw(u, v)と表される
 */
struct edge {
    index_t  src;   /**< 辺の始点u */
    index_t  dst;   /**< 辺の終点v */
    union {
        weight_t w;     /**< 辺(u, v)への重み(コスト) */
        capacity_t c;   /**< 辺(u, v)の容量 */
    };
    edge() = default;
    edge(index_t src, index_t dst) : src(src), dst(dst), w(1) {}
    edge(index_t src, index_t dst, weight_t w) : src(src), dst(dst), w(w) {}
};



using edges_t    = std::vector<edge>;      /**< グラフG=(V, E)の辺集合E   */
using vertices_t = std::vector<vertex>;    /**< グラフG=(V, E)の頂点集合V */
using array_t    = std::vector<weight_t>;  /**< 重みwの配列  */
using indices_t  = std::vector<index_t>;   /**< 頂点の添字配列 */
using matrix_t   = std::vector<array_t>;   /**< グラフGの隣接行列表現(および表行列表現) */
using graph_t    = std::vector<edges_t>;   /**< グラフGの隣接リスト表現(こちらを主に使用する) */



//****************************************
// 関数の定義
//****************************************

/**< @brief 優先度付きキューをmin優先度付きキューにするための < 演算子定義 */
static bool operator < (const edge& e, const edge& f) { return e.w > f.w; }



/**
 * @brief  Primのアルゴリズム
 *
 * @note   Primのアルゴリズムは、グラフの最短路を求めるDijkstraのアルゴリズムとほとんど同じように動作する
 *         Primのアルゴリズムは集合Aの辺が常に1つの木を形成するという性質を持つ. この木は任意の根rから開始し、Vの頂点全体を張るまで成長する
 *         各ステップでは、Aの頂点とある孤立点(Aの辺と接続していない頂点)を連結する軽い辺を木Aに加える
 *         Aに対して安全な辺だけがこの規則によってAに加えられるから、アルゴリズムが終了したとき、Aの辺は最小全域木を形成する
 *         各ステップでは木の重みの増加を限りなく小さく抑える辺を用いて木を成長させるので、これは貪欲戦略である
 *
 * @note   優先度付きキューの優先度更新を行わないため、優先度付きキューが空になるまでに行われる挿入の回数はΟ(E)であるが、
 *         EXTRACT-MIN呼び出し時に、黒頂点であれば無視をすることで、全体としての実行時間をΟ(ElgV)としている
 * 
 * @param  const graph_t& G グラフG
 * @param  index_t        r 最小全域木の根
 */
std::pair<edges_t, weight_t> prim(const graph_t& G, index_t r)
{
    std::int32_t n = G.size();
    std::size_t m = 0;
    for (auto& es : G) { m += es.size(); }
    std::vector<std::int32_t> visited(n);
    edges_t A; weight_t w;

    
    for (index_t u = 0; u < n; u++) {
        visited[u] = false;  // 各頂点を白色に初期化
    }
    std::priority_queue<edge> Q;
    Q.push(edge(limits::nil, r, w = 0));    // 根rはキーを0に設定する
    while (!Q.empty()) {
        edge e = Q.top(); Q.pop();          // 軽い辺を取り出す
        index_t u = e.dst;
        if (visited[u]) { continue; }       // 取り出した辺が安全な辺ではない場合、再びループに戻り条件判定を行う
        
        for (auto&& f : G[u]) {             // uと隣接し、木に属さない各頂点vの更新を行う
            if (!visited[f.dst/*頂点v*/]) { Q.push(f); }
        }
        visited[u] = true;                  // 頂点uを黒色に彩色し、
        w += e.w;                           // 最小重みを更新する
        if (e.src != limits::nil) {  // アルゴリズムが終了したとき、min優先度付きキューは空であり、
            A.emplace_back(e);       // Gに対する最小全域木AはA = { (v, v.π) : v ∈ V - { r } }である  
        }
    }
    return std::make_pair(A, w);
}


//****************************************
// 名前空間の終端
//****************************************

GRAPH_END



//****************************************
// エントリポイント
//****************************************

int main(void)
{
    using namespace std;
    int n;   cin >> n;
    graph::graph_t G; G.resize(n);

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int k;
            cin >> k;
            if (k != -1) {
                G[i].emplace_back(i, j, k);
            }
        }
    }

    auto mst = prim(G);
    cout << mst.second << endl;
    
    return 0;
}

Compiler output:
a.cc:43:25: error: 'int32_t' in namespace 'std' does not name a type
   43 | using weight_t   = std::int32_t;  /**< 辺(u, v)への重みwを表す型 */
      |                         ^~~~~~~
a.cc:44:25: error: 'int32_t' in namespace 'std' does not name a type
   44 | using index_t    = std::int32_t;  /**< 頂点vの添字を表す型       */
      |                         ^~~~~~~
a.cc:45:20: error: 'weight_t' does not name a type; did you mean 'wint_t'?
   45 | using capacity_t = weight_t;      /**< 辺(u, v)の容量を表す型    */
      |                    ^~~~~~~~
      |                    wint_t
a.cc:51:20: error: 'numeric_limits' is not a member of 'std'
   51 |         inf = std::numeric_limits<weight_t>::max() / 3,  /**< @brief 辺が存在しない場合に使用される値     */
      |                    ^~~~~~~~~~~~~~
a.cc:51:35: error: 'weight_t' was not declared in this scope; did you mean 'wint_t'?
   51 |         inf = std::numeric_limits<weight_t>::max() / 3,  /**< @brief 辺が存在しない場合に使用される値     */
      |                                   ^~~~~~~~
      |                                   wint_t
a.cc:51:46: error: '::max' has not been declared; did you mean 'std::max'?
   51 |         inf = std::numeric_limits<weight_t>::max() / 3,  /**< @brief 辺が存在しない場合に使用される値     */
      |                                              ^~~
      |                                              std::max
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:13:
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: 'std::max' declared here
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
a.cc:52:20: error: 'numeric_limits' is not a member of 'std'
   52 |         nil = std::numeric_limits<index_t>::min() / 3,   /**< @brief 先行点が存在しない場合に使用される値 */
      |                    ^~~~~~~~~~~~~~
a.cc:52:35: error: 'index_t' was not declared in this scope
   52 |         nil = std::numeric_limits<index_t>::min() / 3,   /**< @brief 先行点が存在しない場合に使用される値 */
      |                                   ^~~~~~~
a.cc:52:45: error: '::min' has not been declared; did you mean 'std::min'?
   52 |         nil = std::numeric_limits<index_t>::min() / 3,   /**< @brief 先行点が存在しない場合に使用される値 */
      |                                             ^~~
      |                                             std::min
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: 'std::min' declared here
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
a.cc:64:6: warning: elaborated-type-specifier for a scoped enum must not use the 'struct' keyword
   64 | enum struct vcolor : std::int32_t {
      | ~~~~ ^~~~~~
      |      ------
a.cc:64:13: error: use of enum 'vcolor' without previous declaration
   64 | enum struct vcolor : std::int32_t {
      |             ^~~~~~
a.cc:64:20: error: expected unqualified-id before ':' token
   64 | enum struct vcolor : std::int32_t {
      |                    ^
a.cc:75:9: error: 'weight_t' does not name a type; did you mean 'wint_t'?
   75 |         weight_t d;       /**< 始点sからの距離  */
      |         ^~~~~~~~
      |         wint_t
a.cc:76:9: error: 'weight_t' does not name a type; did you mean 'wint_t'?
   76 |         weight_t key;     /**< Primのアルゴリズムにおいて木に属するある頂点とを結ぶ重み */
      |         ^~~~~~~~
      |         wint_t
a.cc:78:5: error: 'index_t' does not name a type
   78 |     index_t pi;           /**< 先行頂点(の添字) */
      |     ^~~~~~~
a.cc:80:9: error: 'vcolor' does not name a type
   80 |         vcolor color;     /**< 頂点の色        */
      |         ^~~~~~
a.cc: In constructor 'graph::vertex::vertex()':
a.cc:84:16: error: class 'graph::vertex' does not have any field named 'd'
   84 |     vertex() : d(0), pi(0), color(vcolor::white)/*, f(0)*/ {}
      |                ^
a.cc:84:22: error: class 'graph::vertex' does not have any field named 'pi'
   84 |     vertex() : d(0), pi(0), color(vcolor::white)/*, f(0)*/ {}
      |                      ^~
a.cc:84:29: error: class 'graph::vertex' does not have any field named 'color'
   84 |     vertex() : d(0), pi(0), color(vcolor::white)/*, f(0)*/ {}
      |                             ^~~~~
a.cc:84:35: error: 'vcolor' has not been declared
   84 |     vertex() : d(0), pi(0), color(vcolor::white)/*, f(0)*/ {}
      |                                   ^~~~~~
a.cc: At global scope:
a.cc:93:5: error: 'index_t' does not name a type
   93 |     index_t  src;   /**< 辺の始点u */
      |     ^~~~~~~
a.cc:94:5: error: 'index_t' does not name a type
   94 |     index_t  dst;   /**< 辺の終点v */
      |     ^~~~~~~
a.cc:96:9: error: 'weight_t' does not name a type; did you mean 'wint_t'?
   96 |         weight_t w;     /**< 辺(u, v)への重み(コスト) */
      |         ^~~~~~~~
      |         wint_t
a.cc:97:9: error: 'capacity_t' does not name a type
   97 |         capacity_t c;   /**< 辺(u, v)の容量 */
      |         ^~~~~~~~~~
a.cc:100:17: error: expected ')' before 'src'
  100 |     edge(index_t src, index_t dst) : src(src), dst(dst), w(1) {}
      |         ~       ^~~~
      |                 )
a.cc:101:17: error: expected ')' before 'src'
  101 |     edge(index_t src, index_t dst, weight_t w) : src(src), dst(dst), w(w) {}
      |         ~       ^~~~
      |                 )
a.cc:108:32: error: 'weight_t' was not declared in this scope; did you mean 'wint_t'?
  108 | using array_t    = std::vector<weight_t>;  /**< 重みwの配列  */
      |                                ^~~~~~~~
      |                                wint_t
a.cc:108:40: error: template argument 1 is invalid
  108 | using array_t    = std::vector<weight_t>;  /**< 重みwの配列  */
      |                                        ^
a.cc:108:40: error: template argument 2 is invalid
a.cc:109:32: error: 'index_t' was not declared in this scope
  109 | using indices_t  = std::vector<index_t>;   /**< 頂点の添字配列 */
      |                                ^~~~~~~
a.cc:109:39: error: template argument 1 is invalid
  109 | using indices_t  = std::vector<index_t>;   /**< 頂点の添字配列 */
      |                                       ^
a.cc:109:39: error: template argument 2 is invalid
a.cc:110:32: error: 'array_t' was not declared in this scope
  110 | using matrix_t   = std::vector<array_t>;   /**< グラフGの隣接行列表現(および表行列表現) */
      |                                ^~~~~~~
a.cc:110:39: error: template argument 1 is invalid
  110 | using matrix_t   = std::vector<array_t>;   /**< グラフGの隣接行列表現(および表行列表現) */
      |                                       ^
a.cc:110:39: error: template argument 2 is invalid
a.cc: In function 'bool graph::operator<(const edge&, const edge&)':
a.cc:120:66: error: 'const struct graph::edge' has no member named 'w'
  120 | static bool operator < (const edge& e, const edge& f) { return e.w > f.w; }
      |                                                                  ^
a.cc:120:72: error: 'const struct graph::edge' has no member named 'w'
  120 | static bool operator < (const edge& e, const edge& f) { return e.w > f.w; }
      |                                                                        ^
a.cc: At global scope:
a.cc:139:20: error: 'weight_t' was not declared in this scope; did you mean 'wint_t'?
  139 | std::pair<edges_t, weight_t> prim(const graph_t& G, index_t r)
      |                    ^~~~~~~~
      |                    wint_t
a.cc:139:28: error: template argument 2 is invalid
  139 | std::pair<edges_t, weight_t> prim(const graph_t& G, index_t r)
      |                            ^
a.cc:139:53: error: 'index_t' has not been declared
  139 | std::pair<edges_t, weight_t> prim(const graph_t& G, index_t r)
      |                                                     ^~~~~~~
a.cc: In function 'int graph::prim(const graph_t&, int)':
a.cc:141:10: error: 'int32_t' is not a member of 'std'; did you mean 'int32_t'?
  141 |     std::int32_t n = G.size();
      |          ^~~~~~~
In file included from /usr/include/x86_64-linux-gnu/sys/types.h:155,
                 from /usr/include/stdlib.h:514,
                 from /usr/include/c++/14/cstdlib:79,
                 from /usr/include/c++/14/bits/stl_algo.h:71:
/usr/include/x86_64-linux-gnu/bits/stdint-intn.h:26:19: note: 'int32_t' declared here
   26 | typedef __int32_t int32_t;
      |                   ^~~~~~~
a.cc:144:22: error: 'int32_t' is not a member of 'std'; did you mean 'int32_t'?
  144 |     std::vector<std::int32_t> visited(n);
      |                      ^~~~~~~
/usr/include/x86_64-linux-gnu/bits/stdint-intn.h:26:19: note: 'int32_t' declared here
   26 | typedef __int32_t int32_t;
      |                   ^~~~~~~
a.cc:144:29: error: template argument 1 is invalid
  144 |     std::vector<std::int32_t> visited(n);
      |                             ^
a.cc:144:29: error: template argument 2 is invalid
a.cc:144:39: error: 'n' was not declared in this scope
  144 |     std::vector<std::int32_t> visited(n);
      |                                       ^
a.cc:145:16: error: 'weight_t' was not declared in this scope; did you mean 'wint_t'?
  145 |     edges_t A; weight_t w;
      |                ^~~~~~~~
      |                wint_t
a.cc:148:10: error: 'index_t' was not declared in this scope
  148 |     for (index_t u = 0; u < n; u++) {
      |          ^~~~~~~
a.cc:148:25: error: 'u' was not declared in this scope
  148 |     for (index_t u = 0; u < n; u++) {
      |                         ^
a.cc:152:33: error: 'w' was not declared in this scope
  152 |     Q.push(edge(limits::nil, r, w = 0));    // 根rはキーを0に設定する
      |                                 ^
a.cc:155:9: error: 'index_t' was not declared in this scope
  155 |         index_t u = e.dst;
      |         ^~~~~~~
a.cc:156:21: error: 'u' was not declared in this scope
  156 |         if (visited[u]) { continue; }       // 取り出した辺が安