本题为邻接矩阵存储有向图求最短路径问题的深度优先搜索方法。

代码：

#include <iostream>
using namespace std;
const int N = 110;
int Min = 99999999;
int n, e[N][N], book[N] = {0};

void dfs(int cur, int dis)
{
    if(dis > Min)
        return;

    if(cur == n)
    {
        if(dis < Min)
            Min = dis;
        return;
    }

    for(int i = 1; i <= n; i++)
    {
        if(e[cur][i] != 99999999 && book[i] == 0)
        {
            book[i] = 1;
            dfs(i, dis + e[cur][i]);
            book[i] = 0;
        }
    }
    return;
}

int main()
{
    int m;
    cin >> n >> m;

    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            if(i == j)
                e[i][j] = 0;
            else 
                e[i][j] = 99999999;
        }
    }

    int a, b, c;
    for(int i = 1; i <= m; i++)
    {
        cin >> a >> b >> c;
        e[a][b] = c;
    }
    book[1] = 1;
    dfs(1, 0);

    cout << Min << endl;
    return 0;
}

测试用例：

5 8
1 2 2
1 5 10
2 3 3
2 5 7
3 1 4
3 4 4
4 5 5
5 3 3

输出结果：

9