题目描述
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 \(n\) countries on the earth, which are numbered from \(1\) to \(n\). They are connected by \(m\) undirected flights, detailedly the \(i\)-th flight connects the \(u_i\)-th and the \(v_i\)-th country, and it will cost Victor's airplane \(w_i\) 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 \(1\), 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.
输入
The first line of the input contains an integer \(T\), denoting the number of test cases.
In every test case, there are two integers \(n\) and \(m\) in the first line, denoting the number of the countries and the number of the flights.
Then there are \(m\) lines, each line contains three integers \(u_i\), \(v_i\) and \(w_i\), describing a flight.
\(1\leq T\leq 20\).
\(1\leq n\leq 16\).
\(1\leq m\leq 100000\).
\(1\leq w_i\leq 100\).
\(1\leq u_i, v_i \leq n\).
输出
Your program should print \(T\) lines : the \(i\)-th of these should contain a single integer, denoting the minimal amount of fuel for Victor to finish the travel.
很明显的状压DP，注意初始化dp，f即可
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef vector<string> VS;
typedef vector<int> VI;
typedef vector<vector<int>> VVI;
inline int log_2(int x) {return 31-__builtin_clz(x);}
inline int popcount(int x) {return __builtin_popcount(x);}
inline int lowbit(int x) {return x&-x;}
const int N = 16,INF = 0x3f3f3f3f;
int dp[N][N];
int f[1<<N][N];
void solve()
{
memset(dp,0x3f,sizeof dp);
memset(f,0x3f,sizeof f);
int n,m;
cin>>n>>m;
//状压时注意标号
for(int i=0;i<n;++i) dp[i][i] = 0;
for(int i=0;i<m;++i)
{
int u,v,w;
cin>>u>>v>>w;
u--, v--;
dp[u][v] = min(dp[u][v],w);
dp[v][u] = min(dp[v][u],w);
}
for(int k=0;k<n;++k)
for(int i=0;i<n;++i)
for(int j=0;j<n;++j)
if(dp[i][k]!=INF&&dp[k][j]!=INF)
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
f[1][0] = 0;
for(int S=1;S<(1<<n);S++)
{
for(int i=0;i<n;++i)
{
if(!(S>>i&1)) continue;
for(int j=0;j<n;++j)
{
if(S>>j&1) continue;
f[S|(1<<j)][j] = min(f[S|(1<<j)][j],f[S][i]+dp[i][j]);
}
}
}
int ans = INF;
for(int i=0;i<n;++i) ans = min(ans,f[(1<<n)-1][i] + dp[i][0]);
cout<<ans<<'\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int T;
cin>>T;
while(T--)
{
solve();
}
}