题目的主要信息：

• 在一个有 n 个点， m 个边的有向图中，已知每条边长，求出 1 到 n 的最短路径
• 如果 1 无法到 n ，输出 -1
• 图没有自环，可能有重边

方法一：floyd算法

具体做法：

可以用floyd算法计算任意两个节点之间的最短路径，然后取1-n的即可。用矩阵w表示任意两个节点之间的最短路径，初始化自己到自己为0，其余都是INT_MAX，然后用图的邻接矩阵来初始化矩阵w，选择边的最小值。

进行floyd算法时，首先枚举中转点，然后枚举起点和终点，当起点到中转点且中转点到终点的路径都存在时，比较最小值收缩路径。

class Solution {
public:
    void floyd(vector<vector<int>>& w, int n){
        for(int k = 1; k <= n; k++){ //枚举中转点
            for(int i = 1; i <= n; i++){ //枚举起点
                for(int j = 1; j <= n; j++){ //枚举终点 
                    if(w[i][k] != INT_MAX && w[k][j] != INT_MAX) //只有当这两条边存在时才可能替换
                        w[i][j] = min(w[i][j], w[i][k] + w[k][j]); //收缩路径
                }
            }
        }
    }
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        vector<vector<int> > w(n + 1, vector<int>(n + 1, INT_MAX)); //记录任意两点之间的最小路径
        for(int i = 1; i <= n; i++) //自己到自己为0
            w[i][i] = 0;
        for(int i = 0; i < m; i++){ //更新有直接连接的边为最小边
            int x = graph[i][0];
            int y = graph[i][1];
            int z = graph[i][2];
            w[x][y] = min(z, w[x][y]);
        }
        floyd(w, n); 
        return w[1][n] == INT_MAX ? -1 : w[1][n]; //有可能有达不到的情况
    }
};

复杂度分析：

• 时间复杂度：$O(n^3)O(n^3)$，floyd算法最坏情况进行了三次循环
• 空间复杂度：$O(n^2)O(n^2)$，额外记录每个点到点之间最短路径的矩阵

方法二：Dijkstra算法

具体做法：

上述是任意节点间的最短路径，复杂度较大，我们也可以用单源最短路径算法Dijkstra算法。

Dijkstra算法算是贪心思想实现的，首先把起点到所有点的距离存下来找个最短的，然后松弛一次再找出最短的，所谓的松弛操作就是，遍历一遍看通过刚刚找到的距离最短的点作为中转站会不会更近，如果更近了就更新距离，这样把所有的点找遍之后就存下了起点到其他所有点的最短距离。

class Solution {
public:
    int dijkstra(vector<vector<int>>& w, int n){
        vector<bool> vis(n + 1, false); //记录某个节点是否被访问过
        vector<int> dis(n + 1, INT_MAX); //记录1到其他所有节点的最短路径
        dis[1] = 0;
        for(int i = 1; i <= n; i++){ //迭代n次
            int temp = -1; //每次找到最短距离最小且未被更新的点temp
            for(int j = 1; j <= n; j++)
                if(!vis[j] && (temp == -1 || dis[j] < dis[temp]))
                    temp = j;
            vis[temp] = true; //标记更新
            for(int j = 1; j <= n; j++) //用已更新的temp更新其他的点
                if(w[temp][j] != INT_MAX && dis[temp] != INT_MAX) //二者有路径次才可以用来更新
                    dis[j] = min(dis[j], dis[temp] + w[temp][j]);
        }
        return dis[n];
    }
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        vector<vector<int> > w(n + 1, vector<int>(n + 1, INT_MAX)); //邻接矩阵
        for(int i = 1; i <= n; i++) //自己到自己为0
            w[i][i] = 0;
        for(int i = 0; i < m; i++){ //更新有直接连接的边为最小边
            int x = graph[i][0];
            int y = graph[i][1];
            int z = graph[i][2];
            w[x][y] = min(z, w[x][y]);
        }
        int res = dijkstra(w, n); //单源最短路径算法
        return res == INT_MAX ? -1 : res; //排除不可达
    }
};

复杂度分析：

• 时间复杂度：$O(n^2)O(n^2)$，Dijkstra算法最坏两层遍历
• 空间复杂度：$O(n^2)O(n^2)$，最大空间为记录边的邻接矩阵w