Language: C++

#include <iostream>
#include <limits>
#include <map>
#include <vector>

using namespace std;

template <typename N = std::size_t, typename E = std::size_t>
class DenseGraph {
public:
    using NodeType = N;
    using EdgeType = E;
    using NeighborListType = std::vector<std::size_t>;

    DenseGraph(const std::size_t size, bool undirected = true) noexcept
        : neighbor_list_(size)
        , undirected_(undirected)
        , nodes_(size)
    {
    }

    void connect(const std::size_t from, const std::size_t to, const EdgeType edge) noexcept
    {
        const std::size_t new_size = std::max(from, to) + 1;

        if (neighbor_list_.size() < new_size) {
            neighbor_list_.resize(new_size);
            nodes_.resize(new_size);
        }

        if (undirected_) {
            neighbor_list_[from].push_back(to);
            edges_[std::make_pair(std::min(from, to), std::max(from, to))] = edge;
        } else {
            neighbor_list_[from].push_back(to);
            neighbor_list_[to].push_back(from);
            edges_[std::make_pair(from, to)] = edge;
        }
    }

    void disconnect(const std::size_t from, const std::size_t to) noexcept
    {
        if (undirected_) {
            neighbor_list_[from].erase(to);
            edges_.erase(std::make_pair(std::min(from, to), std::max(from, to)));
        } else {
            neighbor_list_[from].erase(to);
            neighbor_list_[to].erase(from);
            edges_.erase(std::make_pair(from, to));
        }
    }

    const NodeType& node(const std::size_t index) const noexcept
    {
        return nodes_.at(index);
    }

    const EdgeType& edge(const std::size_t from, const std::size_t to) const noexcept
    {
        if (undirected_) {
            auto key = std::make_pair(std::min(from, to), std::max(from, to));
            return edges_.at(key);
        } else {
            auto key = std::make_pair(from, to);
            return edges_.at(key);
        }
    }

    const NeighborListType&
    neighbor(const std::size_t index) const noexcept
    {
        return neighbor_list_[index];
    }

    std::size_t size() const noexcept
    {
        return neighbor_list_.size();
    }

private:
    using EdgeMap = std::map<std::pair<std::size_t, std::size_t>, EdgeType>;

    std::vector<NeighborListType> neighbor_list_;

    EdgeMap edges_;

    std::vector<NodeType> nodes_;

    bool undirected_;
};

template <typename GraphType>
std::vector<std::vector<int>> warshall_floyd(const GraphType& graph)
{
    const std::size_t n = graph.size();

    std::vector<std::vector<int>> distance(n, std::vector<int>(n, std::numeric_limits<int>::max() / 3));

    for (int i = 0; i < n; i++) {
        distance[i][i] = 0;
        for (auto j : graph.neighbor(i)) {
            distance[i][j] = distance[j][i] = graph.edge(i, j);
        }
    }
    for (std::size_t k = 0; k < n; k++) {
        for (std::size_t i = 0; i < n; i++) {
            for (std::size_t j = 0; j < n; j++) {
                distance[i][j] = std::min(distance[i][j], distance[i][k] + distance[k][j]);
            }
        }
    }
    return distance;
}

int main()
{
    int n, m;
    cin >> n >> m;

    DenseGraph<int, int> graph(n, true);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        graph.connect(a - 1, b - 1, c);
    }

    auto distance = warshall_floyd(graph);

    int count = 0;

    for (int from = 0; from < n; from++) {
        for (int to : graph.neighbor(from)) {
            if (graph.edge(from, to) > distance[from][to]) {
                count++;
            }
        }
    }
    cout << count << endl;
}

Compiler output:
a.cc: In member function 'void DenseGraph<N, E>::disconnect(std::size_t, std::size_t)':
a.cc:44:39: error: no matching function for call to 'std::vector<long unsigned int>::erase(const std::size_t&)'
   44 |             neighbor_list_[from].erase(to);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
In file included from /usr/include/c++/14/vector:66,
                 from a.cc:4:
/usr/include/c++/14/bits/stl_vector.h:1536:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::erase(const_iterator) [with _Tp = long unsigned int; _Alloc = std::allocator<long unsigned int>; iterator = std::vector<long unsigned int>::iterator; const_iterator = std::vector<long unsigned int>::const_iterator]'
 1536 |       erase(const_iterator __position)
      |       ^~~~~
/usr/include/c++/14/bits/stl_vector.h:1536:28: note:   no known conversion for argument 1 from 'const std::size_t' {aka 'const long unsigned int'} to 'std::vector<long unsigned int>::const_iterator'
 1536 |       erase(const_iterator __position)
      |             ~~~~~~~~~~~~~~~^~~~~~~~~~
/usr/include/c++/14/bits/stl_vector.h:1564:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::erase(const_iterator, const_iterator) [with _Tp = long unsigned int; _Alloc = std::allocator<long unsigned int>; iterator = std::vector<long unsigned int>::iterator; const_iterator = std::vector<long unsigned int>::const_iterator]'
 1564 |       erase(const_iterator __first, const_iterator __last)
      |       ^~~~~
/usr/include/c++/14/bits/stl_vector.h:1564:7: note:   candidate expects 2 arguments, 1 provided
a.cc:47:39: error: no matching function for call to 'std::vector<long unsigned int>::erase(const std::size_t&)'
   47 |             neighbor_list_[from].erase(to);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~
/usr/include/c++/14/bits/stl_vector.h:1536:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::erase(const_iterator) [with _Tp = long unsigned int; _Alloc = std::allocator<long unsigned int>; iterator = std::vector<long unsigned int>::iterator; const_iterator = std::vector<long unsigned int>::const_iterator]'
 1536 |       erase(const_iterator __position)
      |       ^~~~~
/usr/include/c++/14/bits/stl_vector.h:1536:28: note:   no known conversion for argument 1 from 'const std::size_t' {aka 'const long unsigned int'} to 'std::vector<long unsigned int>::const_iterator'
 1536 |       erase(const_iterator __position)
      |             ~~~~~~~~~~~~~~~^~~~~~~~~~
/usr/include/c++/14/bits/stl_vector.h:1564:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::erase(const_iterator, const_iterator) [with _Tp = long unsigned int; _Alloc = std::allocator<long unsigned int>; iterator = std::vector<long unsigned int>::iterator; const_iterator = std::vector<long unsigned int>::const_iterator]'
 1564 |       erase(const_iterator __first, const_iterator __last)
      |       ^~~~~
/usr/include/c++/14/bits/stl_vector.h:1564:7: note:   candidate expects 2 arguments, 1 provided
a.cc:48:37: error: no matching function for call to 'std::vector<long unsigned int>::erase(const std::size_t&)'
   48 |             neighbor_list_[to].erase(from);
      |             ~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~
/usr/include/c++/14/bits/stl_vector.h:1536:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::erase(const_iterator) [with _Tp = long unsigned int; _Alloc = std::allocator<long unsigned int>; iterator = std::vector<long unsigned int>::iterator; const_iterator = std::vector<long unsigned int>::const_iterator]'
 1536 |       erase(const_iterator __position)
      |       ^~~~~
/usr/include/c++/14/bits/stl_vector.h:1536:28: note:   no known conversion for argument 1 from 'const std::size_t' {aka 'const long unsigned int'} to 'std::vector<long unsigned int>::const_iterator'
 1536 |       erase(const_iterator __position)
      |             ~~~~~~~~~~~~~~~^~~~~~~~~~
/usr/include/c++/14/bits/stl_vector.h:1564:7: note: candidate: 'std::vector<_Tp, _Alloc>::iterator std::vector<_Tp, _Alloc>::erase(const_iterator, const_iterator) [with _Tp = long unsigned int; _Alloc = std::allocator<long unsigned int>; iterator = std::vector<long unsigned int>::iterator; const_iterator = std::vector<long unsigned int>::const_iterator]'
 1564 |       erase(const_iterator __first, const_iterator __last)
      |       ^~~~~
/usr/include/c++/14/bits/stl_vector.h:1564:7: note:   candidate expects 2 arguments, 1 provided