Language: C++

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


#include <iostream>
#include <utility>
#include <algorithm>
#include <vector>



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

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

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

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

    bool operator < (const edge& e) const { return w < e.w; }
    bool operator > (const edge& e) const { return w > e.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の隣接リスト表現(こちらを主に使用する) */



namespace graph {  // グラフ用名前空間...そのうちこのファイルを覆い尽くす予定
    enum {  // namespace graphによってscopedではあるが強く型付けされたenum(strongly-typed enum)ではない
    inf = std::numeric_limits<weight_t>::max() * 2 / 3,  /**< @brief 辺が存在しない場合に使用される値     */
    nil = std::numeric_limits<index_t>::min() * 2 / 3,   /**< @brief 先行点が存在しない場合に使用される値 */
};
}



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

/**
 * @brief  動的計画アルゴリズムであるFloyd-Warshallアルゴリズム
 *
 * @note   Floyd-Warshallアルゴリズムでは最短路の中間頂点を考える. ここで、単純道p = <v0,v1,...,vl>のv0とvl以外の頂点、
 *         すなわち、集合{ v1,v2,...,v(l-1) }の任意の頂点が中間(intermediate)頂点である
 *
 *         Floyd-Warshallアルゴリズムは以下の観察に基づいている. Gの頂点集合がV = { 0,1,...,n-1 }であるという仮定の下で、
 *         あるkに対して頂点の部分集合{ 0,1,...k }を考える. 任意の頂点対i,j ∈ Vに対して、iからjへの道で、そのすべての中間頂点が
 *         集合 { 0,1,...,k }に属するものをすべて考え、その中で最小の重みを持つ道をpとする. (道pは単純である)
 *
 *         Floyd-Warshallアルゴリズムは、道pと、中間頂点がすべて集合{ 0,1,...,k-1 }に属する(という条件の下での)iからjへの最短路との関係を解明する
 *         この関係はkが道pの中間頂点であるかどうかに依存する
 *
 *         * kが道pの中間頂点でなければ、pの中間頂点はすべて集合{ 0,1,...,k-1 }に属している. したがって、中間頂点がすべて集合{ 0,1,..,k-1 }に属する
 *           頂点iからjへの最短路は、中間頂点がすべて集合{ 0,1,...,k }に属するiからjへの最短路である
 *
 *         * kが道pの中間頂点ならば、pをi~(p1)~>k~(p2)~>jと分解する. p1は中間頂点がすべて集合{ 0,1,...,k }に属するiからjへの最短路である
 *           実際には、もう少し強い言明が成立する. 頂点kは道p1上の中間頂点ではないから、p1の中間頂点はすべて集合{ 0,1,...,k-1 }に属する.
 *           したがって、 p1は中間頂点がすべて集合{ 0,1,...,k-1 }に属するiからkへの最短路である
 *           同様に、p2は中間頂点がすべて集合{ 0,1,...,k-1 }に属する頂点kから頂点jへの最短路である
 *
 *         上の観察に基づいて、最短路の推定値を再帰的に定式化する. 中間頂点がすべて集合{ 0,...,k }に属する頂点iからjへの最短路の重みをdij^(k+1)とする
 *         k = -1のとき、-1より大きい番号を持つ中間頂点を通らない頂点iから頂点jへの道は中間頂点を1つも持たない. このような道は高々1本の辺しかもたないから、
 *         dij^(0) = wijである. よって、dij^(k+1)の再帰的な定義
 *           dij^(k+1) = { wij                            k = -1のとき
 *                       min(dij^(k), dik^(k) + djk^(k))  k >= 0のとき }
 *         を得る. 任意の道において、すべての中間頂点は集合{ 0,..,n-1 }に属するから、行列D^(n-1) = (dij^(n-1))が最終的な解を与える
 *         すなわち、すべてのi,j ∈ Vに対して、dij^(d) = δ(i, j)が成立する. 実際には、この場合を頂点0,1,...,k-1のみを使う場合に帰着させる
 *
 *         i,j,k = 0,1,...,n-1に対してdij^(k)を計算するからFloyd-WarshallアルゴリズムではΘ(n^3)の領域が必要であるが、
 *         前回の履歴のみを必要とするので、すべての肩添字を落としただけの手続きも正しく、Θ(n^2)の領域で十分である
 *
 * @note   3重のfor分における操作はΟ(1)時間で実行できるから、このアルゴリズムの実行時間はΘ(n^3)である
 *         このコードはタイトであって、複雑なデータ構造を含まず、Θ-記法に隠された定数は小さい
 *         したがって、Floyd-Warshallアルゴリズムは結構大きな入力グラフに対しても非常に実用的である
 *
 */
matrix_t floydwarshall(const matrix_t& W)
{
    std::int32_t n = W.size();  // n = W.rows
    matrix_t D(n, array_t(n, graph::inf)); for (index_t i = 0; i < n; i++) { std::copy(W[i].begin(), W[i].end(), D[i].begin()); D[i][i] = 0; }
    for (index_t k = 0; k < n; k++) {
        for (index_t i = 0; i < n; i++) {
            for (index_t j = 0; j < n; j++) {
                // 任意の実数a != ∞に対して、a + ∞ = ∞ + a = ∞(また、a + (-∞) = (-∞) + a = (-∞))を仮定している
                if (D[i][k] != graph::inf && D[k][j] != graph::inf) {
                    D[i][j] = std::min(D[i][j], D[i][k] + D[k][j]);
                }
            }
        }
    }
    return D;
}



int main(void)
{
    using namespace std;
    using namespace graph;
    
    int n, e, u, v, c;
    cin >> n >> e;
    matrix_t W(n, array_t(n, inf));
    for (int i = 0; i < n; i++) { W[i][i] = 0; }

    for (int i = 0; i < e; i++) {
        cin >> u >> v >> c;
        W[u][v] = c;
    }

    matrix_t D = floydwarshall(W);

    bool neg = false;
    for (int i = 0; i < n; i++) { if (D[i][i] < 0) { neg = true; } }

    if (neg) {
        cout << "NEGATIVE CYCLE" << endl;
    }
    else {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (j) cout << " ";
                if (D[i][j] == inf) cout << "INF";
                else                cout << D[i][j];
            }
            cout << endl;
        }
    }
    
    return 0;
}

Compiler output:
a.cc:17:23: error: 'int32_t' in namespace 'std' does not name a type
   17 | using weight_t = std::int32_t;  /**< 辺(u, v)への重みwを表す型 */
      |                       ^~~~~~~
a.cc:18:23: error: 'int32_t' in namespace 'std' does not name a type
   18 | using index_t  = std::int32_t;  /**< 頂点vの添字を表す型       */
      |                       ^~~~~~~
a.cc:26:6: warning: elaborated-type-specifier for a scoped enum must not use the 'struct' keyword
   26 | enum struct color : std::int32_t {
      | ~~~~ ^~~~~~
      |      ------
a.cc:26:13: error: use of enum 'color' without previous declaration
   26 | enum struct color : std::int32_t {
      |             ^~~~~
a.cc:26:19: error: expected unqualified-id before ':' token
   26 | enum struct color : std::int32_t {
      |                   ^
a.cc:37:9: error: 'weight_t' does not name a type; did you mean 'wint_t'?
   37 |         weight_t d;       /**< 始点sからの距離  */
      |         ^~~~~~~~
      |         wint_t
a.cc:38:9: error: 'weight_t' does not name a type; did you mean 'wint_t'?
   38 |         weight_t key;     /**< Primのアルゴリズムにおいて木に属するある頂点とを結ぶ重み */
      |         ^~~~~~~~
      |         wint_t
a.cc:40:5: error: 'index_t' does not name a type
   40 |     index_t pi;           /**< 先行頂点(の添字) */
      |     ^~~~~~~
a.cc:42:9: error: 'color' does not name a type
   42 |         color _color;     /**< 頂点の色        */
      |         ^~~~~
a.cc: In constructor 'vertex::vertex()':
a.cc:46:16: error: class 'vertex' does not have any field named 'd'
   46 |     vertex() : d(0), pi(0), _color(color::white)/*, f(0)*/ {}
      |                ^
a.cc:46:22: error: class 'vertex' does not have any field named 'pi'
   46 |     vertex() : d(0), pi(0), _color(color::white)/*, f(0)*/ {}
      |                      ^~
a.cc:46:29: error: class 'vertex' does not have any field named '_color'
   46 |     vertex() : d(0), pi(0), _color(color::white)/*, f(0)*/ {}
      |                             ^~~~~~
a.cc:46:36: error: 'color' has not been declared
   46 |     vertex() : d(0), pi(0), _color(color::white)/*, f(0)*/ {}
      |                                    ^~~~~
a.cc: At global scope:
a.cc:55:5: error: 'index_t' does not name a type
   55 |     index_t  src;   /**< 辺の始点u */
      |     ^~~~~~~
a.cc:56:5: error: 'index_t' does not name a type
   56 |     index_t  dst;   /**< 辺の終点v */
      |     ^~~~~~~
a.cc:57:5: error: 'weight_t' does not name a type; did you mean 'wint_t'?
   57 |     weight_t w;     /**< 辺(u, v)への重み(コスト) */
      |     ^~~~~~~~
      |     wint_t
a.cc:59:17: error: expected ')' before 'src'
   59 |     edge(index_t src, index_t dst) : src(src), dst(dst), w(1) {}
      |         ~       ^~~~
      |                 )
a.cc:60:17: error: expected ')' before 'src'
   60 |     edge(index_t src, index_t dst, weight_t w) : src(src), dst(dst), w(w) {}
      |         ~       ^~~~
      |                 )
a.cc: In member function 'bool edge::operator<(const edge&) const':
a.cc:62:52: error: 'w' was not declared in this scope
   62 |     bool operator < (const edge& e) const { return w < e.w; }
      |                                                    ^
a.cc:62:58: error: 'const struct edge' has no member named 'w'
   62 |     bool operator < (const edge& e) const { return w < e.w; }
      |                                                          ^
a.cc: In member function 'bool edge::operator>(const edge&) const':
a.cc:63:52: error: 'w' was not declared in this scope
   63 |     bool operator > (const edge& e) const { return w > e.w; }
      |                                                    ^
a.cc:63:58: error: 'const struct edge' has no member named 'w'
   63 |     bool operator > (const edge& e) const { return w > e.w; }
      |                                                          ^
a.cc: At global scope:
a.cc:70:32: error: 'weight_t' was not declared in this scope; did you mean 'wint_t'?
   70 | using array_t    = std::vector<weight_t>;  /**< 重みwの配列  */
      |                                ^~~~~~~~
      |                                wint_t
a.cc:70:40: error: template argument 1 is invalid
   70 | using array_t    = std::vector<weight_t>;  /**< 重みwの配列  */
      |                                        ^
a.cc:70:40: error: template argument 2 is invalid
a.cc:71:32: error: 'index_t' was not declared in this scope
   71 | using indices_t  = std::vector<index_t>;   /**< 頂点の添字配列 */
      |                                ^~~~~~~
a.cc:71:39: error: template argument 1 is invalid
   71 | using indices_t  = std::vector<index_t>;   /**< 頂点の添字配列 */
      |                                       ^
a.cc:71:39: error: template argument 2 is invalid
a.cc:72:32: error: 'array_t' was not declared in this scope
   72 | using matrix_t   = std::vector<array_t>;   /**< グラフGの隣接行列表現(および表行列表現) */
      |                                ^~~~~~~
a.cc:72:39: error: template argument 1 is invalid
   72 | using matrix_t   = std::vector<array_t>;   /**< グラフGの隣接行列表現(および表行列表現) */
      |                                       ^
a.cc:72:39: error: template argument 2 is invalid
a.cc:79:16: error: 'numeric_limits' is not a member of 'std'
   79 |     inf = std::numeric_limits<weight_t>::max() * 2 / 3,  /**< @brief 辺が存在しない場合に使用される値     */
      |                ^~~~~~~~~~~~~~
a.cc:79:31: error: 'weight_t' was not declared in this scope; did you mean 'wint_t'?
   79 |     inf = std::numeric_limits<weight_t>::max() * 2 / 3,  /**< @brief 辺が存在しない場合に使用される値     */
      |                               ^~~~~~~~
      |                               wint_t
a.cc:79:42: error: '::max' has not been declared; did you mean 'std::max'?
   79 |     inf = std::numeric_limits<weight_t>::max() * 2 / 3,  /**< @brief 辺が存在しない場合に使用される値     */
      |                                          ^~~
      |                                          std::max
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:8:
/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:80:16: error: 'numeric_limits' is not a member of 'std'
   80 |     nil = std::numeric_limits<index_t>::min() * 2 / 3,   /**< @brief 先行点が存在しない場合に使用される値 */
      |                ^~~~~~~~~~~~~~
a.cc:80:31: error: 'index_t' was not declared in this scope
   80 |     nil = std::numeric_limits<index_t>::min() * 2 / 3,   /**< @brief 先行点が存在しない場合に使用される値 */
      |                               ^~~~~~~
a.cc:80:41: error: '::min' has not been declared; did you mean 'std::min'?
   80 |     nil = std::numeric_limits<index_t>::min() * 2 / 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:127:1: error: 'matrix_t' does not name a type
  127 | matrix_t floydwarshall(const matrix_t& W)
      | ^~~~~~~~
a.cc: In function 'int main()':
a.cc:153:5: error: 'matrix_t' was not declared in this scope
  153 |     matrix_t W(n, array_t(n, inf));
      |     ^~~~~~~~
a.cc:154:35: error: 'W' was not declared in this scope
  154 |     for (int i = 0; i < n; i++) { W[i][i] = 0; }
      |                                   ^
a.cc:158:9: error: 'W' was not declared in this scope
  158 |         W[u][v] = c;
      |         ^
a.cc:161:13: error: expected ';' before 'D'
  161 |     matrix_t D = floydwarshall(W);
      |             ^~
      |             ;
a.cc:164:39: error: 'D' was not declared in this scope
  164 |     for (int i = 0; i < n; i++) { if (D[i][i] < 0) { neg = true; } }
      |                                       ^
a.cc:173:21: error: 'D' was not declared in this scope
  173 |                 if (D[i][j] == inf) cout << "INF";
      |                     ^