题解 | #单源最短路#

抄的题解：知道思路，但细节上不会处理

难点

dijksta

• open，closed数组如何表示
• 如何查找该节点的邻近节点

#include <vector>
class Solution {

  public:
    int dijkstra(vector<vector<int>>& w, int n) {
        vector<bool> visited(n + 1, false);
        vector<int> dis(n + 1, INT_MAX);
        dis[1] = 0;
        for (int i = 1; i <= n; i++) {
            int temp = -1;
            for (int j = 1; j <= n; j++) {
                if (!visited[j] && (temp == -1 || dis[j] < dis[temp])) {
                    temp = j;
                }
            }
            visited[temp] = true;
            for (int j = 1; j <= n; j++) {
                if (w[temp][j] != INT_MAX && dis[temp] != INT_MAX) {
                    dis[j] = min(dis[j], dis[temp] + w[temp][j]);
                }
            }
        }

        return dis[n];
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型 顶点数
     * @param m int整型 边数
     * @param graph int整型vector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少​
     * @return int整型
     */
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        // write code here
        vector<vector<int>> w(n + 1, vector<int>(n + 1, INT_MAX));
        for (int i = 0; i < n; i++) {
            w[i][i] = 0;
        }

        for (int i = 0; i < m; i++) {
            int vertex1 = graph[i][0];
            int vertex2 = graph[i][1];
            int weight = graph[i][2];
            w[vertex1][vertex2] = min(weight, w[vertex1][vertex2]);
        }
        int res = dijkstra(w, n);
        return res == INT_MAX ? -1 : res;

    }


};