題干：

After trying hard for many years, Victor has finally received a pilot license. To have a celebration, he intends to buy himself an airplane and fly around the world. There are?nn?countries on the earth, which are numbered from?11?to?nn. They are connected by?mm?undirected flights, detailedly the?ii-th flight connects the?uiui-th and the?vivi-th country, and it will cost Victor's airplane?wiwi?L fuel if Victor flies through it. And it is possible for him to fly to every country from the first country.?

Victor now is at the country whose number is?11, he wants to know the minimal amount of fuel for him to visit every country at least once and finally return to the first country.

Input

The first line of the input contains an integer?TT, denoting the number of test cases.?
In every test case, there are two integers?nn?and?mm?in the first line, denoting the number of the countries and the number of the flights.?

Then there are?mm?lines, each line contains three integers?uiui,?vivi?and?wiwi, describing a flight.?

1≤T≤201≤T≤20.?

1≤n≤161≤n≤16.?

1≤m≤1000001≤m≤100000.?

1≤wi≤1001≤wi≤100.?

1≤ui,vi≤n1≤ui,vi≤n.

Output

Your program should print?TT?lines : the?ii-th of these should contain a single integer, denoting the minimal amount of fuel for Victor to finish the travel.

Sample Input

1 3 2 1 2 2 1 3 3

Sample Output

10

題目大意：

有n個(gè)城市，在n個(gè)城市之間有m條雙向路，每條路有一個(gè)距離，現(xiàn)在問從1號(hào)城市出發(fā)，去游覽其它的2到n號(hào)城市最后回到1號(hào)城市的最短路徑（題目數(shù)據(jù)保證1可以直接或間接到達(dá)其他城市）。（n<=16）

解題報(bào)告：

因?yàn)槊總€(gè)點(diǎn)可以走多次所以不是哈密頓回路，這一個(gè)特性也就決定了我們可以用floyd求最短路。

dp[sta][v]代表走過狀態(tài)為sta并且當(dāng)前站在v這個(gè)城市的最小距離。最后加一個(gè)回到原點(diǎn)的距離就行了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; int n,m; int head[MAX],tot; int dis[22][22]; int dp[1<<18][18]; bool ok[22]; struct Edge {int fr,to,ne;int w; } e[MAX]; void add(int u,int v,int w) {e[++tot].fr = u;e[tot].to = v;e[tot].w = w;e[tot].ne = head[u];head[u] = tot; } void floyd() {for(int k = 0; k<n; k++) {for(int i = 0; i<n; i++) {for(int j = 0; j<n; j++) {dis[i][j] = min(dis[i][j],dis[i][k] + dis[k][j]);}}} } int tsp() {int up = 1<<n;dp[1][0] = 0; for(int sta = 0; sta < up; sta++) {memset(ok,0,sizeof ok);for(int i = 0; i<n; i++) {if((1<<i) & sta) ok[i] = 1;}for(int u = 0; u<n; u++) { //可以if(dp==-1)continue 也可以先初始化成0x3f3f3f3f？？？ for(int v = 0; v<n; v++) {if(ok[v]) continue;dp[sta|(1<<v)][v] = min(dp[sta|(1<<v)][v],dp[sta][u] + dis[u][v]);}}}int ans = 0x3f3f3f3f;for(int i = 0; i<n; i++) {ans = min(ans,dp[up-1][i] + dis[i][0]);}return ans; } int main() {int t;cin>>t;while(t--) {scanf("%d%d",&n,&m);//init tot=0;memset(dis,0x3f,sizeof dis);memset(dp,0x3f,sizeof dp);for(int i = 0; i<n; i++) head[i] = -1,dis[i][i] = 0;for(int u,v,w,i = 1; i<=m; i++) {scanf("%d%d%d",&u,&v,&w);u--,v--;add(u,v,w);add(v,u,w);if(w < dis[u][v]) dis[u][v] = dis[v][u] = w;}floyd();cout << tsp() << endl;}return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【HDU - 5418】Victor and World（tsp旅行商问题，状压dp，floyd最短路，图论）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。