test/aoj/jag/bipartite_matching.test.cpp

// competitive-verifier: PROBLEM https://onlinejudge.u-aizu.ac.jp/problems/2251
#include <algorithm>
#include <iostream>
#include "flow/bipartite_matching.hpp"
#include "graph/floyd_warshall.hpp"
#include "graph/matrix_graph.hpp"

constexpr int Inf = 1000000003;

int main(void) {
    while (true) {
        int n, m, l;
        std::cin >> n >> m >> l;
        if (!n) break;
        matrix_graph<int> g(n, Inf);
        while (m--) {
            int u, v, w;
            std::cin >> u >> v >> w;
            g.add_edges(u, v, w);
        }
        floyd_warshall(g);
        std::vector<std::pair<int, int>> q(l);
        for (auto &[a, b] : q) std::cin >> a >> b;
        std::sort(q.begin(), q.end(), [](auto l, auto r) { return l.second < r.second; });
        BipartiteMatching hk(l, l);
        for (int i = 0; i < l; ++i) {
            auto [a, b] = q[i];
            for (int j = i + 1; j < l; ++j) {
                auto [c, d] = q[j];
                if (b + g[a][c] <= d) hk.add_edge(i, j);
            }
        }
        std::cout << l - hk.matching() << '\n';
    }

    return 0;
}