题意：有中文版的
分析：(出题人的解题报告)我们首先需要预处理出任意两个国家之间的最短距离，因为数据范围很小，所以直接用Floyd就行了。之后，我们用f[S][i]表示访问国家的情况为S，当前最后访问的一个国家是i所需要的最小总油量，其中，S的二进制表示记录了访问国家的情况，S在二进制表示下的第i位（不管是从左往右还是从右往左都可以）如果是1则表示第i个国家被访问过了，否则表示第i个国家没有被访问过，那么f[S|(1<<i)][i]=min(f[S][j]+f[i][j])，其中i和j满足S&(1<<j)=1且S&(1<<i)=0。最开始时，除了f[1][1]是0，其他情况都是无穷大，之后先枚举S，再枚举i（我验题的时候因为这里搞反结果WA了），那么最终的答案就是min(f[(1<<n)-1][i]+f[i][1])，其中i\in∈[2,n]。总复杂度为O(n^3+n^2*2^n)O(n3+n2∗2n)。
收获：暂时无，TSP没搞懂纯贴模板
代码：
/************************************************
* Author :Running_Time
* Created Time :2015-8-22 18:55:17
* File Name :B.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
int d[17][17];
int dp[(1<<16)+10][17];
int n, m; int work(void) {
for (int k=0; k<n; ++k) {
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) {
d[i][j] = min (d[i][j], d[i][k] + d[k][j]);
}
}
} for (int i=0; i<(1<<n); ++i) {
for (int j=0; j<n; ++j) dp[i][j] = INF;
}
dp[1][0] = 0;
for (int i=0; i<(1<<n); ++i) {
for (int j=0; j<n; ++j) {
if (dp[i][j] != INF) {
for (int k=0; k<n; ++k) {
if (!(i>>k&1)) {
dp[i|(1<<k)][k] = min (dp[i|(1<<k)][k], dp[i][j] + d[j][k]);
}
}
}
}
} int ans = INF;
for (int i=0; i<n; ++i) {
ans = min (ans, dp[(1<<n)-1][i] + d[i][0]);
} return ans;
} int main(void) {
int T; scanf ("%d", &T);
while (T--) {
scanf ("%d%d", &n, &m);
for (int i=0; i<n; ++i) {
for (int j=0; j<n; ++j) d[i][j] = INF;
}
for (int u, v, w, i=1; i<=m; ++i) {
scanf ("%d%d%d", &u, &v, &w); u--, v--;
d[u][v] = min (d[u][v], w);
d[v][u] = min (d[v][u], w);
}
for (int i=0; i<n; ++i) d[i][i] = 0;
printf ("%d\n", work ());
} return 0;
}