#include <iostream>  #include <map>  #include <memory>  #include <new>  #include <stdexcept>

namespace{   enum : int{    MAXVALUE = 9999   };  }

template<typename T>  class Graph{   private:    std::map<T, std::map<T, int>> graph_;    std::map<T, std::map<T, T>> path_;    std::map<T, std::map<T, int>> distance_;        unsigned int node_number_;        void floyd_warshall()noexcept;        public:     using map_type = std::map<T, std::map<T, int>>;          using map_iter = typename std::map<T, std::map<T, int>>::const_iterator;          using iter = typename std::map<T, int>::const_iterator;          template<typename Ty, unsigned int N>     Graph(const Ty (&edges)[N][3]);          ~Graph();          template<typename Ty>     void print(const Ty& start, const Ty& end);  };

template<typename T>  template<typename Ty, unsigned int N>  Graph<T>::Graph(const Ty (&edges)[N][3])           :node_number_(N)  {   if(N == 0){    throw std::runtime_error(std::string("there is nothing"));   }      /*for(int i=0; i<N; ++i){    for(int j=0; j<N; ++j){     (this->*graph_)[i][j] = (i == j)　? 0 : ::MAXVALUE; //如果该点的距离为从自身到自身那么距离为0.     }   }*/      for(int j =0; j<N; ++j){    (this->graph_)[edges[j][0]][edges[j][1]] = edges[j][2];   }      map_iter first_ = (this->graph_).cbegin();   for(; first_ != (this->graph_).cend(); ++first_){        map_iter second_ = (this->graph_).cbegin();    for(; second_ != (this->graph_).cend(); ++second_){          if(first_->first == second_->first){      (this->graph_)[first_->first][second_->first] = 0;           }else if((this->graph_)[first_->first][second_->first] > 0){      continue;           }else{      (this->graph_)[first_->first][second_->first] = ::MAXVALUE;     }    }   }      std::cout<<"successful constructor\n";      /*map_iter iter_first = this->graph_.cbegin();   for(; iter_first != this->graph_.cend(); ++iter_first){        std::cout<<iter_first->first<<":  ";    iter iter_second = this->graph_[iter_first->first].cbegin();    for(; iter_second != this->graph_[iter_first->first].cend(); ++iter_second){          std::cout<<iter_second->first<<"--"<<iter_second->second<<"  ";    }        std::cout<<std::endl;   }*/  }

template<typename T>  void Graph<T>::floyd_warshall()noexcept  {   if(this->node_number_ == 0){    throw std::runtime_error(std::string("there nothing in graph"));   }      //注意下面的双重循环:   //first_, second_, 以first_为起点second_为终点不断的查找这两个结点间的距离.    map_iter first_ = (this->graph_).cbegin();   for(; first_ != (this->graph_).cend(); ++first_){        iter second_ = (this->graph_)[first_->first].cbegin();    for(; second_ != (this->graph_)[first_->first].cend(); ++second_){          this->distance_[first_->first][second_->first] = (this->graph_)[first_->first][second_->first];     this->path_[first_->first][second_->first] = 0;    }   }      /*map_iter x = this->distance_.cbegin();   for(; x != this->distance_.cend(); ++x){        std::cout<<x->first<<":  ";    iter y = (this->distance_)[x->first].cbegin();    for(; y != (this->distance_)[x->first].cend(); ++y){          std::cout<<y->first<<"--"<<x->first<<"  ";    }    std::cout<<std::endl;   }*/      map_iter third_ = (this->graph_).cbegin();   map_iter forth_ = (this->graph_).cbegin();   map_iter fifth_ = (this->graph_).begin();      for(; third_ != (this->graph_).cend(); ++third_){        for(; forth_ != (this->graph_).cend(); ++forth_){          for(; fifth_ != (this->graph_).cend(); ++fifth_){            if((this->distance_)[forth_->first][third_->first] != ::MAXVALUE && (this->distance_)[third_->first][fifth_->first] != ::MAXVALUE && (this->distance_)[forth_->first][third_->first]+(this->distance_)[third_->first][fifth_->first]<(this->distance_)[forth_->first][fifth_->first]){       (this->distance_)[forth_->first][fifth_->first] = this->distance_[forth_->first][third_->first] + this->distance_[fifth_->first][third_->first];       (this->path_)[forth_->first][fifth_->first] = third_->first;      }     }    }   }  }

template<typename T>  template<typename Ty>  void Graph<T>::print(const Ty& start, const Ty& end)  {   this->floyd_warshall();  }

template<typename T>  Graph<T>::~Graph()  {   if(!this->graph_.empty()){    this->graph_.clear();   }      if(!this->path_.empty()){    this->path_.clear();   }      if(!this->distance_.empty()){    this->distance_.clear();   }  }

int main()  {   int edges[15][3]={   {1, 2, 2},   {1, 4, 20},   {2, 5, 1},   {3, 1, 3},   {4, 3, 8},   {4, 6, 6},   {4, 7, 4},   {5, 3, 4},   {5, 8, 3},   {6, 3, 1},   {7, 8, 1},   {8, 6, 2},   {8, 10, 2},   {9, 7, 2},   {10, 9, 1}   };      Graph<int> my_graph(edges);      my_graph.print(2, 4);      return 0;   }