#include "helpers.cpp"

#include<cstdio>
#include<vector>
#include<queue>
#include<set>

#include <boost/config.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/graphviz.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/breadth_first_search.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <boost/property_map/function_property_map.hpp>

using namespace std;
using namespace boost;

typedef adjacency_list<listS, vecS, bidirectionalS, Vertex, Edge> Graph;
typedef graph_traits<Graph>::vertex_descriptor vertex_t;
typedef graph_traits<Graph>::edge_descriptor edge_t;
typedef graph_traits<Graph>::vertices_size_type Size;

using Predicate = std::function<bool(vertex_t)>;
using Filtered  = boost::filtered_graph<Graph, boost::keep_all, Predicate>;

Graph G;
unsigned N;
vector<Size> d;
set<vertex_t> shortest_vertices;

void do_bfs(vertex_t starting) {
    d.resize(N, 0);
    breadth_first_search(
            G, starting, 
            visitor(
                make_bfs_visitor(record_distances(&d[0], on_tree_edge()))
                ));
}

void make_shortest_graph(Size shortest) {
    std::queue<vertex_t> q;

    for (auto vp = vertices(G); vp.first != vp.second; ++vp.first) {
        if (G[*vp.first].winning && d[*vp.first] == shortest) {
            q.push(*vp.first);
            shortest_vertices.insert(*vp.first);
        }
    }

    while (!q.empty()) {
        vertex_t where = q.front();
        q.pop();

        int where_dis = d[where];

        for (auto in = in_edges(where, G); in.first != in.second; ++in.first) {   
            vertex_t prev = source(*in.first, G);
            int prev_dis = d[prev];
            if (prev_dis + 1 != where_dis) continue;
            if (shortest_vertices.find(prev) != shortest_vertices.end()) continue;
            q.push(prev);
            shortest_vertices.insert(prev);
        }
    }
}

Size get_counter_length() {
    auto is_on_shortest = [](vertex_t vd) {
       return shortest_vertices.find(vd) != shortest_vertices.end();
    };
    Filtered shortest_G(G, boost::keep_all{}, is_on_shortest);

    int N = num_vertices(shortest_G);
    vector<Size> d(N, 0);
    vector<vertex_t> p(N);

    vertex_t starting = get_starting(shortest_G);

    auto min_pushes_diff = make_function_property_map<edge_t>([](edge_t e) {
            return G[target(e, G)].min_pushes - G[source(e, G)].min_pushes > 0 ? 1 : 0;
    });

    dijkstra_shortest_paths(shortest_G, starting,
        predecessor_map(make_iterator_property_map(p.begin(), get(vertex_index, shortest_G))).
        distance_map(make_iterator_property_map(d.begin(), get(vertex_index, shortest_G))).
        weight_map(min_pushes_diff));

    return get_shortest_path(shortest_G, d);
}

int main(int argc , char* argv[]) {
    string filename = argv[1];
    N = read(G, filename);

    vertex_t starting = get_starting(G);

    do_bfs(starting);
    Size shortest = get_shortest_path(G, d);

    make_shortest_graph(shortest);

    printf("%lu\n", get_counter_length());

    return 0;
}
