Графы

//////////////////////////////////////////////////////////////////////////////////////
//По системе односторонних дорог определить, есть ли в ней город, из которого 
//можно добраться до каждого из остальных городов, проезжая не более 100 км.
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <iostream>
#include <limits>
#include <map>
#include <set>
#include <string>
#include <vector>
//////////////////////////////////////////////////////////////////////////////////////
typedef std::string                    T_str;
typedef T_str                          T_vertice;
typedef std::set<T_vertice>            T_vertices_set;
typedef std::vector<T_vertice>         T_vertices;
typedef T_vertices                     T_arc;
typedef std::set<T_arc>                T_arcs_set;
typedef int                            T_weight;
typedef std::map<T_arc, T_weight>      T_arcs_weights;
typedef std::map<T_vertice, T_weight>  T_row;
typedef std::map<T_vertice, T_row>     T_adjacency_matr;
//////////////////////////////////////////////////////////////////////////////////////
struct T_greater_in_row
{
    T_row  row_;
    //------------------------------------------------------------------------
    T_greater_in_row(T_row  row) : row_(row)
    {}
    //------------------------------------------------------------------------
    bool operator() (T_vertice  A, T_vertice  B)                  
    {
        return row_[A] > row_[B];
    }
};
//////////////////////////////////////////////////////////////////////////////////////
void  print_matr
    (
        const T_adjacency_matr&  matr,
        const T_weight           WEIGHT_MAX,
        const T_str              INFINITY_NAME
    )
{  
    for(T_adjacency_matr::const_iterator  vert_row_it = matr.begin(); 
        vert_row_it != matr.end(); ++vert_row_it)
    {
        for(T_row::const_iterator  vert_weight_it = vert_row_it->second.begin();
            vert_weight_it != vert_row_it->second.end(); ++vert_weight_it)
        {
            if(vert_weight_it->second == WEIGHT_MAX)
            {
                std::cout << '\t'
                          << INFINITY_NAME;
            }
            else
            {
                std::cout << '\t'
                          << vert_weight_it->second;
            }
        }
        std::cout << std::endl
                  << std::endl
                  << std::endl;
    }
}
//////////////////////////////////////////////////////////////////////////////////////
T_vertices  get_vertices(const T_arcs_set&  arcs_set)
{
    T_vertices_set  vertices_set;
    for(T_arcs_set::const_iterator  arc_it = arcs_set.begin(); arc_it != arcs_set.end();
        ++ arc_it)
    {
        vertices_set.insert(*arc_it->begin());
        vertices_set.insert(*arc_it->rbegin());
    }
    return T_vertices(vertices_set.begin(), vertices_set.end()); 
}
//////////////////////////////////////////////////////////////////////////////////////
T_adjacency_matr  get_adjacency_matr
    (
        const T_vertices&      vertices, 
        const T_arcs_weights&  arcs_weights,
        const T_weight         WEIGHT_MAX
    )
{
    T_adjacency_matr  adjacency_matr;
    for(size_t  i = 0; i < vertices.size(); ++i)
    {
        for(size_t  j = 0; j < vertices.size(); ++j)
        {
            adjacency_matr[vertices[i]][vertices[j]] = WEIGHT_MAX;
        }
    }
 
    for(T_arcs_weights::const_iterator   arcs_weights_elem_it = arcs_weights.begin(); 
        arcs_weights_elem_it != arcs_weights.end(); ++arcs_weights_elem_it)
    {
        adjacency_matr
            [arcs_weights_elem_it->first.front()]
            [arcs_weights_elem_it->first.back() ] = arcs_weights_elem_it->second;
    }
    return  adjacency_matr;
}
//////////////////////////////////////////////////////////////////////////////////////
T_row  dijkstra
    (
        const T_vertice&   vertice_start,
        T_vertices         vertices,
        T_adjacency_matr&  adjacency_matr,
        const T_weight     WEIGHT_MAX
    )
{    
    T_row       weights_min_from_vert_start = adjacency_matr[vertice_start];     
    T_vertices  S;
    S.push_back     (vertice_start);
    vertices.erase  (std::find(vertices.begin(), vertices.end(), vertice_start));    
    while(!vertices.empty())
    {
        //Из элементов vertices выбираем тот, для которого значение weights_min_from_vert_start
        //минимально.
        std::make_heap(vertices.begin(), vertices.end(), 
                       T_greater_in_row(weights_min_from_vert_start));
 
        T_vertice  w = vertices.front();
 
        S.push_back     (w);
        vertices.erase  (vertices.begin());
        for(T_vertices::const_iterator  v_it = vertices.begin();
            v_it != vertices.end(); ++v_it)
        {
            T_weight&  for_w    = weights_min_from_vert_start  [w];
            T_weight&  for_v    = weights_min_from_vert_start  [*v_it];
            T_weight&  for_w_v  = adjacency_matr               [w][*v_it];
 
            if(   for_w    != WEIGHT_MAX  
               && for_w_v  != WEIGHT_MAX
               && for_w + for_w_v < for_v)
            {
                for_v = for_w + for_w_v;
            }
        }
    }
    return  weights_min_from_vert_start;
}
//////////////////////////////////////////////////////////////////////////////////////
void print_vertice_distant_not_further_than
    (
        const T_weight     max_path_weight,
        const T_vertices&  vertices,
        T_adjacency_matr&  adjacency_matr,
        const T_weight     WEIGHT_MAX
    )
{    
    for(T_vertices::const_iterator  v_it = vertices.begin();
        v_it != vertices.end(); ++v_it)
    {
        T_row  weights_min_from_v = dijkstra
                                        (
                                            *v_it,
                                            vertices,
                                            adjacency_matr,
                                            WEIGHT_MAX
                                        );
 
        T_vertices  vertices_for_v(vertices);
        std::sort(vertices_for_v.begin(), vertices_for_v.end(), 
                  T_greater_in_row(weights_min_from_v));
 
        //Удаляем первую вершину, так как это сама *v_it, расстояние до которой
        //от самой себя бесконечность.
        vertices_for_v.erase(vertices_for_v.begin());
 
        if(weights_min_from_v[vertices_for_v.front()] <= max_path_weight)
        {
            std::cout << "Город, расположенный от остальных не далее "
                      << max_path_weight 
                      << " км: "
                      << *v_it
                      << "."
                      << std::endl;
            return;
        }
 
    }
    std::cout << "В данной системе дорог нет города, "               
              << "расположенного от остальных не далее "
              << max_path_weight 
              << " км."
              << std::endl;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));
    int n = 0;
    do
    {
        std::cout << "Введите количество дуг ориентированного взвешенного графа > 0: ";
        std::cin >> n;
    }while(n <= 0);
 
    T_arcs_set      arcs_set;
    T_arcs_weights  arcs_weights;
    const T_weight  WEIGHT_MAX = std::numeric_limits<T_weight>::max();
    const T_str     INFINITY_NAME = "INF";
    std::cout << "Введите "
              << n
              << " дуг ориентированного взвешенного графа."
              << std::endl
              <<"Вершины в дуге не должны быть одинаковыми.";
    do
    {
        std::cout << std::endl
                  << "дуга #"
                  << arcs_set.size() + 1
                  << ":"
                  << std::endl
                  << '\t'
                  << "начало  : ";
        T_vertice  v1;
        std::cin >> v1;
        T_arc  arc_cur;
        arc_cur.push_back(v1);
        
        T_vertice  v2;
        std::cout << '\t'
                  << "конец   : ";
        std::cin >> v2;        
        arc_cur.push_back(v2);        
        if(   arc_cur.size() == 2
           && arc_cur.front() != arc_cur.back())
        {
            if(arcs_set.insert(arc_cur).second)
            {
                T_weight  arc_weight;
                do
                {
                    std::cout << '\t'
                              << '\t'
                              << "вес >= 0"                              
                              << ": ";
                    std::cin >> arc_weight;
                }while(arc_weight < 0 || WEIGHT_MAX <= arc_weight);
                arcs_weights[arc_cur] = arc_weight;
            }
        }        
    }while(static_cast<int>(arcs_set.size()) < n);
 
    T_vertices  vertices = get_vertices(arcs_set);
 
    T_adjacency_matr  adjacency_matr = get_adjacency_matr(vertices, arcs_weights, WEIGHT_MAX);
 
    std::cout << std::endl
              << "Матрица смежности графа ("
              << INFINITY_NAME 
              << " означает бесконечность):"
              << std::endl;
 
    print_matr(adjacency_matr, WEIGHT_MAX, INFINITY_NAME);
 
    std::cout << "Вершины графа:"
              << std::endl
              << '\t';
 
    std::copy(vertices.begin(), vertices.end(), 
              std::ostream_iterator<T_vertice>(std::cout, "\t"));
    std::cout << std::endl;
 
    const int  max_path_weight = 100;
    
    print_vertice_distant_not_further_than
        (
            max_path_weight,
            vertices,
            adjacency_matr,
            WEIGHT_MAX
        );
}