题解 | #单源最短路#

#define MAX 999999

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int 顶点数
     * @param m int 边数
     * @param graph intvector<vector<>> 一维3个数据，表示顶点到另外一个顶点的边长度是多少​
     * @return int
     */
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        int dis[n];
        for(auto &c:dis)
            c = MAX;

        dis[0] = 0;

        for(int i = 0;i<n-1;i++)
            for(int j = 0;j<m;j++){
                dis[graph[j][1]-1] = min(dis[graph[j][1]-1], dis[graph[j][0]-1]+graph[j][2]);
        }

        return dis[n-1]==MAX? -1:dis[n-1];

    }
};