#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> graph(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> graph[i][j];
        }
    }
    
    // dp[mask][i]: 最短路径长度，其中mask表示已访问的村庄集合，i表示当前所在村庄
    vector<vector<int>> dp(1 << n, vector<int>(n, INT_MAX));
    
    // 初始化：从村庄0出发
    dp[1][0] = 0;
    
    // 遍历所有状态
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if (dp[mask][i] == INT_MAX) continue;
            
            // 尝试访问下一个村庄j
            for (int j = 0; j < n; j++) {
                // 如果j不在当前访问集合中
                if (!(mask & (1 << j))) {
                    int new_mask = mask | (1 << j);
                    dp[new_mask][j] = min(dp[new_mask][j], dp[mask][i] + graph[i][j]);
                }
            }
        }
    }
    
    // 找到回到起点的最短路径
    int ans = INT_MAX;
    for (int i = 0; i < n; i++) {
        if (dp[(1 << n) - 1][i] != INT_MAX && graph[i][0] != 0) {
            ans = min(ans, dp[(1 << n) - 1][i] + graph[i][0]);
        }
    }
    
    cout << ans << endl;
    return 0;
}

算法解释：

1. 状态定义：dp[mask][i] 表示当前已访问的村庄集合为 mask，当前在村庄 i 的最短路径长度。

2. 初始化：从村庄0（商店所在地）出发，所以 dp[1][0] = 0（二进制1表示只访问了村庄0）。

3. 状态转移：对于每个状态 (mask, i)，尝试访问下一个未访问的村庄 j，更新状态 (mask | (1<<j), j)。

4. 最终结果：在所有村庄都被访问的状态 (1<<n)-1 下，找到回到村庄0的最短路径。

时间复杂度：O(2^N * N^2)，对于 N < 40 可以接受。

示例运行： 输入：

3
0 2 1
1 0 2
2 1 0

输出：

3

路径：0→2→1→0 或 0→1→2→0，总距离为 3。