Let \(d_{i,j}\) denote the length of the shortest path from vertex \(i\) to vertex \(j\). Then, the answer coincides with the minimum value of \(d_{p_1,p_2}+d_{p_2,p_3}+\dots+d_{p_{N-1},p_N}\) over all permutations \((p_1,p_2,\dots,p_N)\) of \((1,2,\dots,N)\).

Proof

It is clear that a walk created by connecting the shortest paths from \(p_1\) to \(p_2\), from \(p_2\) to \(p_3\), \(\dots\), from \(p_{N-1}\) to \(p_N\) in this order satisfies the conditions. It suffices to show that, conversely, there is always a walk that satisfies the conditions and has the minimum possible total weight of the edges traversed (simply called an optimal solution from now on) that can be represented in the form above.

Let the walk \(x_1\rightarrow x_2\rightarrow \dots \rightarrow x_k\) be an optimal solution. Here, we can assume \(x_1\neq x_k\) (when \(x_1=x_k\), the entire path is a single cycle, but since there is no negative cycle, we can choose an edge with non-negative weight, and by removing that edge, we can “cut open” the cycle to obtain a walk that is not a cycle while keeping the set of vertices traversed unchanged). Therefore, from \(x_1,x_2,\dots,x_k\), we can select \(N\) vertices including \(x_1\) and \(x_k\) without duplication (i.e., so that each of \(1,2,\dots,N\) appears once). For the parts not selected, it is clearly optimal to connect them with the shortest path between the two nearest selected vertices, so this walk is represented in the form described above.

Consider the following dynamic programming approach:

• \(\mathrm{dp}[S][i]\): The minimum total weight of the edges traversed for walks that start from any vertex and end at vertex \(i\), with the set of vertices traversed being \(S\).

For the transition, we can search for the next vertex \(j\) to visit among the vertices not yet visited and update \(\mathrm{dp}[S\cup \{j\}][j]\leftarrow \min\{\mathrm{dp}[S\cup \{j\}][j],\mathrm{dp}[S][i]+d_{i,j}\}\).

Therefore, by precomputing \(d_{i,j}\) for all \(i,j\) using the Floyd-Warshall algorithm or similar, the problem can be solved with a total computational complexity of \(O(N^3+2^NN^2)\).

Sample Implementation (C++):

#include<bits/stdc++.h>

using namespace std;

const int inf = 1 << 30;

void chmin(int &a, int b) { a = min(a, b); }

int main() {
    int n, m;
    cin >> n >> m;
    vector d(n, vector<int>(n, inf));
    for (int i = 0; i < n; i++) d[i][i] = 0;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        --u, --v;
        d[u][v] = w;
    }
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (d[i][k] == inf or d[k][j] == inf) continue;
                chmin(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    vector dp(1 << n, vector<int>(n, inf));
    for (int i = 0; i < n; i++) dp[1 << i][i] = 0;
    for (int bit = 1; bit < (1 << n) - 1; bit++) {
        for (int i = 0; i < n; i++) {
            if (~bit >> i & 1) continue;
            if (dp[bit][i] == inf) continue;
            for (int j = 0; j < n; j++) {
                if (bit >> j & 1) continue;
                if (d[i][j] == inf) continue;
                chmin(dp[bit | 1 << j][j], dp[bit][i] + d[i][j]);
            }
        }
    }
    int ans = inf;
    for (int i = 0; i < n; i++) {
        chmin(ans, dp[(1 << n) - 1][i]);
    }
    if (ans == inf) cout << "No" << endl;
    else cout << ans << endl;
}