test/aoj/grl/floyd_warshall.test.cpp

• View this file on GitHub
• Last update: 2025-06-13 13:22:21+09:00
• Problem: https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_C

Depends on

• ワーシャルフロイド法 (lib/graph/floyd_warshall.hpp)
• 隣接行列 (lib/graph/matrix_graph.hpp)
• lib/template/template.hpp

Code

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/GRL_1_C
#include "graph/floyd_warshall.hpp"
#include <cstdint>
#include <iostream>
#include <string>
#include "graph/matrix_graph.hpp"

int main(void) {
    int v, e;
    std::cin >> v >> e;
    matrix_graph<std::int64_t> g(v, INF);
    while (e--) {
        int s, t, d;
        std::cin >> s >> t >> d;
        g.add_edge(s, t, d);
    }
    floyd_warshall(g);
    for (int i = 0; i < v; ++i) {
        if (g[i][i] < 0) {
            std::cout << "NEGATIVE CYCLE\n";
            return 0;
        }
    }

    for (int i = 0; i < v; ++i) {
        for (int j = 0; j < v; ++j) {
            if (g[i][j] >= INF / 2) std::cout << "INF";
            else std::cout << g[i][j];
            if (j == v - 1) std::cout << '\n';
            else std::cout << ' ';
        }
    }

    return 0;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/resolver.py", line 291, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 242, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 479, in update
    self._resolve(pathlib.Path(included), included_from=path)
  File "/home/runner/.local/lib/python3.12/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 286, in _resolve
    raise BundleErrorAt(path, -1, "no such header")
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: graph/floyd_warshall.hpp: line -1: no such header

Test cases

Env	Name	Status	Elapsed	Memory
g++	00_sample_00	AC	2 ms	4 MB
g++	00_sample_01	AC	2 ms	4 MB
g++	00_sample_02	AC	2 ms	4 MB
g++	01_small_00	AC	2 ms	4 MB
g++	01_small_01	AC	2 ms	4 MB
g++	02_corner_00	AC	2 ms	3 MB
g++	02_corner_01	AC	2 ms	4 MB
g++	02_corner_02	AC	2 ms	3 MB
g++	02_corner_03	AC	2 ms	4 MB
g++	02_corner_04	AC	2 ms	4 MB
g++	02_corner_05	AC	2 ms	4 MB
g++	02_corner_06	AC	2 ms	4 MB
g++	03_medium_00	AC	2 ms	4 MB
g++	03_medium_01	AC	2 ms	4 MB
g++	04_dag_00	AC	2 ms	4 MB
g++	04_dag_01	AC	2 ms	3 MB
g++	04_dag_02	AC	2 ms	4 MB
g++	04_dag_03	AC	2 ms	4 MB
g++	04_dag_04	AC	3 ms	4 MB
g++	05_ring_00	AC	2 ms	4 MB
g++	05_ring_01	AC	2 ms	3 MB
g++	05_ring_02	AC	2 ms	4 MB
g++	05_ring_03	AC	2 ms	4 MB
g++	05_ring_04	AC	2 ms	4 MB
g++	06_grid_00	AC	2 ms	4 MB
g++	06_grid_01	AC	2 ms	3 MB
g++	06_grid_02	AC	2 ms	4 MB
g++	06_grid_03	AC	2 ms	3 MB
g++	06_grid_04	AC	2 ms	4 MB
g++	07_complete_00	AC	2 ms	3 MB
g++	07_complete_01	AC	2 ms	3 MB
g++	07_complete_02	AC	4 ms	4 MB
g++	07_complete_03	AC	5 ms	4 MB
g++	07_complete_04	AC	7 ms	4 MB
g++	08_random_00	AC	2 ms	4 MB
g++	08_random_01	AC	2 ms	4 MB
g++	08_random_02	AC	2 ms	4 MB
g++	08_random_03	AC	2 ms	3 MB
g++	08_random_04	AC	2 ms	4 MB
g++	08_random_05	AC	2 ms	4 MB
g++	08_random_06	AC	2 ms	3 MB
g++	08_random_07	AC	2 ms	4 MB
g++	08_random_08	AC	3 ms	4 MB
g++	09_maximum_00	AC	3 ms	4 MB
g++	09_maximum_01	AC	3 ms	4 MB
g++	09_maximum_02	AC	8 ms	4 MB
g++	09_maximum_03	AC	3 ms	4 MB
g++	09_maximum_04	AC	3 ms	4 MB
g++	09_maximum_05	AC	4 ms	4 MB
g++	09_maximum_06	AC	3 ms	4 MB

Back to top page