题意整理：

题目以边的形式给出一个有向图，要求找到图中指定两个点（1，n）中的最短路径
为了便于后续操作，我们先将给出的边权数组转化为点对之间的距离，对于没有边链接的距离为INT_MAX，对于重边取得较小值。

方法一：DFS（超时）

核心思想：

首先，我们需要从起点1开始，往能够前往的点进行搜索。此处需要维持一个vis数组记录哪些点已经进行了访问，如果再次访问将不对其进行访问，因为边权都是正值，明显对一个点再次访问不会得到更好的答案。当到达点n时停止搜索，更新答案。
由于对边的访问没有特殊顺序，所有可能每次都以最差路径为开始进行遍历，时间复杂度很高，无法通过所有测试案例

核心代码：

class Solution {
public:
    int ans, len;

    void dfs(vector<vector<int>>& f, vector<int>& vis, int p, int d) {
        if(p == len) {//找到n点
            ans = min(ans,d);
            return;
        }
        if(d >= ans) {//剪枝
            return;
        }
        vis[p] = d;//记录
        for(int i = 1; i <= len; ++i) {
            if((vis[i] == -1 || vis[i] > d + f[p][i]) && f[p][i] != INT_MAX) {
                //确保不访问已经不会作为答案的路线
                dfs(f, vis, i, d + f[p][i]);
            }
        }
    }

    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        vector<vector<int>> f(n, vector<int>(n, INT_MAX));//距离数组
        len = n - 1;
        ans = INT_MAX;//初始化答案为最大值
        for(vector<int>& it : graph) {
            f[it[0] - 1][it[1] - 1] = min(f[it[0] - 1][it[1] - 1],it[2]);//填入边权
        }
        vector<int> vis(n, -1);
        dfs(f, vis, 0, 0);
        return ans == INT_MAX ? -1 : ans;
    }
};

复杂度分析：

时间复杂度：。最坏的情况下，会对每个点的边都进行一次搜索,
空间复杂度：,使用了大小为的空间记录边，大小为的空间记录访问情况，以及最坏为的递归栈

方法二：dijkstra算法

核心思想：

方法一之所以会超时，主要在于每次遍历点都只是基于点的编号，没有利用其他性质，可能会出现一个点遍历多次的情况，且每次都需要对大量点进行重新更新。实际上，对于点对之间的距离，有个很好的算法既dijkstra算法。
算法思路：使用一个d数组记录从源点出发到其他点的距离。
初始化 ,其他
循环n次,每次在未标记节点中，选出d值最小的节点 x ,对其打上标记，对于从x出发的所有边（x, y）进行更新,这使得每次更新只对少数点进行更新，且不会对后续点产生影响，因为每次都是选择d最小的点。

核心代码：

class Solution {
public:
    int findShortestPath(int n, int m, vector<vector<int> >& graph) {
        vector<vector<int>> f(n, vector<int>(n, INT_MAX));//距离数组
        for(vector<int>& it : graph) {
            f[it[0] - 1][it[1] - 1] = min(f[it[0] - 1][it[1] - 1],it[2]);//填入边权
        }
        vector<int> vis(n, 0);//记录访问情况
        vector<int> d(n, INT_MAX);//记录距离
        d[0] = 0;
        for(int i = 0; i < n; ++i) {
            //遍历n次n个点
            int x = 0, p = INT_MAX;
            for(int y = 0; y < n; ++y) {
                if(vis[y] == 0 && d[y] < p) {
                    //找到最小x值
                    p = d[y];
                    x = y;
                }
            }
            if(p == INT_MAX) {
                //无法继续找到点，结束掉
                break;
            }
            vis[x] = 1;
            for(int y = 1; y < n; ++y) {
                //对点进行更新
                if(f[x][y] != INT_MAX) {
                    d[y] = min(d[y], d[x] + f[x][y]);
                }
            }
        }
        return d[n - 1] == INT_MAX ? -1 : d[n - 1];
    }
};

复杂度分析：

时间复杂度：，遍历了n次，每次选取最小x需要花费时间
空间复杂度：,使用了大小为的空间记录边,大小为的空间记录访问情况,大小为的空间记录距离