题解 | #最长路径#

从牛牛所占有的所有星球出发，向外扩张，当第一次触碰到牛妹的星球时，跳出循环。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param serialP intvector 牛牛占领的p个星球的编号
     * @param serialQ intvector 牛妹占领的q个星球的编号
     * @param path intvector<vector<>> m条隧道，每条隧道有三个数分别是ui,vi,wi。ui,vi分别是隧道的两边星球的编号，wi是它们之间的距离
     * @param nn int 星球个数n
     * @return int
     */

    

    int Length(vector<int>& serialP, vector<int>& serialQ, vector<vector<int>>& path, int nn) {
        // write code here
        vector<int> visited(nn);
        unordered_set<int> p; //牛牛的地盘
        unordered_set<int> q; //牛妹的地盘
        vector<vector<pair<int, int>>> point_to(nn); //路径连接
        for (auto i : serialQ) q.emplace(i - 1);  //记录牛妹的地盘

        for (int index = 0; index < path.size();++index) {
            point_to[path[index][0] - 1].push_back({ path[index][1] - 1,path[index][2] });
            point_to[path[index][1] - 1].push_back({ path[index][0] - 1,path[index][2] });
        }

        auto mycomp2 = [](const pair<int, int>&a, const pair<int, int>&b)->bool {
            return a.second > b.second;
        };  //自定义路径比较算法

        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(mycomp2)> que(mycomp2);  //优先队列，每次挤出距离最近的星球

        for (auto i : serialP) {
            que.push({ i-1,0 });
            p.emplace(i-1);
        }  //牛牛的地盘
        int ans = -1;
        int cur_index, next_index, cur_cost;
        while (!que.empty()) {
            auto cur = que.top();
            que.pop();
            cur_index = cur.first;
            cur_cost = cur.second;

            if (q.find(cur_index) != q.end()) {
                ans = cur_cost;
                break;
            }  //找到牛妹的地盘了，跳出循环
            if (visited[cur_index]) continue;
            visited[cur_index] = 1;
            for (auto next : point_to[cur_index]) {
                next_index = next.first;
                if (visited[next_index] || p.find(next_index) != p.end()) continue; //如果下一个点已经计算出最短路径了或者属于牛牛的地盘则跳过
                que.push({ next_index,cur_cost + next.second });
            }
        }
        return ans;
    }
};