题解 | #单源最短路#

class Solution {
public:

    //思路：
    //从1开始遍历，第一轮将与1直接相连的结点直接记录在list数组中
    //然后遍历与1相连的数据，看与其直接相连的数据的距离+其与1的距离，是否小于list中的距离，如果小于，则更新list
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        // write code here
        int answer = -1;
        auto temp = graph;

        //存放距离1最近的距离
        vector<int> list(501,-1) ;
        //1到1的距离为0
        list[1] = 0;
        //记录1所能到达的点
        deque<int> q;
        q.push_back(1);
        //q为空时，说明从1能走到的点全被遍历过了
        while(!q.empty()){
            int n = q.front();
            q.pop_front();
            //遍历所有路径，如果该路径的起点是当前点
            //则先判断当前点1是否到达过，   如果没有到达，则直接记录1到当前路径终点的距离
            //                            如果达到过，则先比较，如果之前的路径中1到当前路径的终点更远，则更新1到当前路径终点的距离
            for(auto node : temp){
                if(node[0] == n){
                    if(list[node[1]] == -1){
                        list[node[1]] = list[n] + node[2];
                        q.push_back(node[1]);
                    }else if(list[node[1]] > list[n] + node[2]){
                        list[node[1]] = list[n] + node[2];
                    }
                }
            }
        }
        answer = list[n];
        return answer;
    }
};

欢迎各位大佬畅所欲言，I'm so vegetable

我感觉这个思路，在遍历temp时，会遍历很多遍历过的数据，这会浪费很多时间

但是我又怕删除后，会影响结果

比如，在走一条不是最佳的路径组合时，删除了其中一条路径段

然后在走最佳路径时，因为其中的路径段被删除了，从而得不到最佳路径了

求大佬指点orz