HDU 5418（动态规划-状压dp+floyd算法)

古城微笑少年丶 2022-06-01 05:16 256阅读 0赞

问题描述:

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

题目题意:给我们n个城市，m条边（表示花费），问从城市1游玩所有城市回到1的最小费用。

题目分析:先用floyd算法跑去任意俩点的花费，然后dp，dp\[i\]\[j\]，i表示当前的状态（去了那几个城市），j表示最后一个城市是那个。

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    using namespace std;
    
    const int inf=1e9+7;
    int G[20][20];
    int dp[1<<16][20];
    int main()
    {
        int t;
        scanf("%d",&t);
        while (t--) {
            int n,m;
            scanf("%d%d",&n,&m);
            for (int i=1;i<=n;i++){
                for (int j=1;j<=n;j++){
                    if (i==j) G[i][j]=0;
                    else G[i][j]=inf;
                }
            }
            for (int i=1;i<=m;i++) {
                int u,v,w;
                scanf("%d%d%d",&u,&v,&w);
                G[u][v]=G[v][u]=min(G[u][v],w);
            }
            for (int i=1;i<=n;i++) {
                for (int j=1;j<=n;j++) {
                    for (int k=1;k<=n;k++) {
                        G[i][j]=min(G[i][j],G[i][k]+G[k][j]);
                    }
                }
            }
            for (int i=1;i<(1<<n);i++) {
                for (int j=1;j<=n;j++) {
                    dp[i][j]=inf;
                }
            }
            dp[1][1]=0;
            for (int i=1;i<(1<<n);i++) {
                for (int j=1;j<=n;j++) {
                    if (dp[i][j]>=inf) continue;
                    for (int k=1;k<=n;k++) {
                        if (!(i&(1<<(k-1)))) {
                            dp[i|(1<<(k-1))][k]=min(dp[i|(1<<(k-1))][k],dp[i][j]+G[j][k]);
                        }
                    }
                }
            }
            int ans=inf;
            for (int i=1;i<=n;i++) {
                ans=min(ans,dp[(1<<n)-1][i]+G[i][1]);
            }
            printf("%d\n",ans);
        }
        return 0;
    }