题解 | #单源最短路#

#include <utility>
#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 顶点数
     * @param m int整型 边数
     * @param graph int整型vector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少​
     * @return int整型
     */
    const int inf = 0x3f3f3f3f;
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        std::map<std::pair<int, int>, int>  roads;
        std::vector<std::pair<bool, int>> symbols_length(n + 1, {false, inf});

        for (const auto &road : graph){
            std::pair<int, int> roads_pair{road[0], road[1]};
            if (roads.find(roads_pair) == roads.end() || roads[roads_pair] > road[2])
                roads[roads_pair] = road[2];
        }
        
        
        auto contiue_condition = [&](std::pair<bool, int> p) -> bool {return (p.first == false && p.second != inf); };
        auto select_condition = [](std::pair<bool, int> a, std::pair<bool, int> b) -> bool {return a.second < b.second && !a.first; };

        symbols_length[1].second = 0;
        while(true) {
            auto continue_bool = std::find_if(symbols_length.begin(), symbols_length.end(), contiue_condition) != symbols_length.end();
            if (continue_bool) {
                auto mix_iterator = std::min_element(symbols_length.begin(), symbols_length.end(), select_condition);
                mix_iterator->first = true;


                auto index = std::distance(std::begin(symbols_length), mix_iterator);
                for (const auto & road : roads) {
                    if (road.first.first == index) {
                        if (symbols_length[road.first.second].second > symbols_length[road.first.first].second + road.second) {
                            symbols_length[road.first.second].second = symbols_length[road.first.first].second + road.second;
                        }
                    }
                }

            } else {
                return symbols_length[n].second == inf ? -1 : symbols_length[n].second;
            }
        }
    }
};