#include <iostream> #include <vector> #include <limits> void shortestpath( const std::vector <std::vector< short> >& paths, int from, std::vector< short>& path){     std:: vector<bool> flags(paths.size(), false);     std:: vector<short> distance(paths.size(), 0);     path.resize(paths.size(), 0);     for(size_t i = 0; i != paths.size(); ++i){         distance[i] = paths[from][i];     }     flags[from] = 1;     int min, pos;     for(size_t i = 1; i != paths.size(); ++i){         pos = -1;         min = std:: numeric_limits<short>::max();         for(size_t j = 0; j != paths.size(); ++j){             if(!flags[j] && distance[j] < min){                 min = distance[j];                 pos = j;             }         }         if(pos == -1)             break;         flags[pos] = true;         for(size_t j = 0; j != paths.size(); ++j){             if(!flags[j] && paths[pos][j] != 0                 && paths[pos][j] < std::numeric_limits <int>:: max()                 && min+paths[pos][j] < distance[j]){                 distance[j] = min + paths[pos][j];                 path[j] = pos;             }         }     }     for(size_t i = 0; i != distance.size(); ++i){         std::cout << distance[i] << " " << std::flush;     }     std::cout << std:: endl; } int main(){     std::cout << "请输入顶点数：" << std::flush;     int sum; std::cin >> sum;     std:: vector<std::vector <short> > paths;     for(int i = 0; i != sum; ++i){         paths.push_back(std:: vector<short>(sum, std::numeric_limits< short>::max()));         paths[i][i] = 0;     }     std::cout << "请输入边数：" << std::flush;     std::cin >> sum;     int vi, vj, weight;     for(int i = 0; i != sum; ++i){         std::cin >> vi >> vj >> weight;         paths[vi][vj] = weight;         paths[vj][vi] = weight;     }     std:: vector<short> path;     shortestpath(paths, 0, path);     std::cout << "最近路径结果为：" << std::flush;     for(size_t i = 0; i != path.size(); ++i){         std::cout << path[i] << " " << std::flush;     }     std::cout << std:: endl;     return 0; }