郊区春游（状压dp)

链接：https://ac.nowcoder.com/acm/contest/134/D
来源：牛客网

今天春天铁子的班上组织了一场春游，在铁子的城市里有n个郊区和m条无向道路，第i条道路连接郊区A_i和B_i，路费是C_i。经过铁子和顺溜的提议，他们决定去其中的R个郊区玩耍（不考虑玩耍的顺序），但是由于他们的班费紧张，所以需要找到一条旅游路线使得他们的花费最少，假设他们制定的旅游路线为V₁, V₂ ,V₃ ... V_R，那么他们的总花费为从V₁到V₂的花费加上V₂到V₃的花费依次类推，注意从铁子班上到V₁的花费和从V_R到铁子班上的花费是不需要考虑的，因为这两段花费由学校报销而且我们也不打算告诉你铁子学校的位置。

链接：https://ac.nowcoder.com/acm/contest/134/D
来源：牛客网

输入描述:

第一行三个整数n, m, R(2 ≤ n ≤ 200, 1 ≤ m ≤ 5000, 2 ≤ R ≤ min(n, 15))。
第二行R个整数表示需要去玩耍的郊区编号。
以下m行每行A

_i

, B

_i

, C

_i

(1 ≤ A

_i

, B

_i 

≤ n, A

_i

≠ B

_i

, C

_i 

≤ 10000)

保证不存在重边。

输出描述:

输出一行表示最小的花费

示例1

输入

复制

4 6 3
2 3 4
1 2 4
2 3 3
4 3 1
1 4 1
4 2 2
3 1 6

输出

复制

3


状压dp，dp[ s ][ i ]表示当前已经游玩的点（R中的点），且终点是 i 的最小花费。预处理出任意两点之间的最短距离。
其中s指的是状态，
比如dp[5][j]的5二进制是101，就是表示当前走过的路径上的目标郊区有0，2，dp[8][j]的话就是有目标郊区3

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn=1e3+100;
const int inf=0x3f3f3f3f;
/*
dp[s][i]表示当前已经游玩的点（R中的点）， 
且终点是 i 的最小花费，s指的是状态 
*/
int dis[maxn][maxn];
int rs[maxn];
int dp[1<<15+2][20];
int n,m,r;
int main(){
    memset(dis,inf,sizeof(dis));
    memset(dp,inf,sizeof(dp));
    cin>>n>>m>>r;
    for(int i=0;i<r;i++){
        cin>>rs[i];
    }
    int x,y,w;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>w;
        dis[x][y]=dis[y][x]=w; 
    }
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j||j==k||i==k){
                    continue;
                } 
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); 
            }
        }
    } 
    memset(dp,inf,sizeof(dp));
    for(int i=0;i<r;i++){
        dp[1<<i][i]=0;
    }
    for(int s=1;s<(1<<r);s++){
        for(int i=0;i<r;i++){
            if(!(s>>i)&1) continue;
            int x=rs[i];
            for(int j=0;j<r;j++){
                if((s>>j)&1){
                    continue;
                } 
                int y=rs[j];
                dp[s|(1<<j)][j]=min(dp[s|(1<<j)][j],dp[s][i]+dis[x][y]);
            }
        }
    }
    int ans=inf;
    for(int i=0;i<r;i++){
        ans=min(ans,dp[(1<<r)-1][i]);
    }
    cout<<ans<<endl;
} 

 再看这一题和上一题是一样的：

n个人在做传递物品的游戏,编号为1−n。
游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。
即物品只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值之间没有联系；
求当物品经过所有n个人后，整个过程的总代价是多少。

Input

第一行为nn，表示共有n个人（2≤n≤16）；
以下为n×n的矩阵，第i+1行、第jj列表示物品从编号为i的人传递到编号为j的人所花费的代价，特别的有第i+1行、第ii列为-1（因为物品不能自己传给自己），其他数据均为正整数(≤10000)。

Output

一个数，为最小的代价总和。

Samples

Input Copy

2
-1 9794
2724 -1

Output

2724

Hint

• 对于50%的数据，n≤11；
• 对于100%的数据，n≤16。

Source

石光中学 2018泉州集训普及组day5


这些都是一样的dp[s][j]是指的是最后经过j，且状态时s的最小花费

#include<iostream>
#include<algorithm>
#include<cstring> 
using namespace std;
const int maxn=20;
int a[maxn][maxn];
int f[(1<<maxn)+10][maxn];
const int inf=0x3f3f3f3f;
int n;
void inint(){
    cin>>n;
    int x; 
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>x;
            if(i!=j) a[i][j]=x;
        }
    }
    memset(f,inf,sizeof(f));
    for(int i=0;i<n;i++){
        f[1<<i][i]=0;
    }
}
int main(){
    inint();
    for(int i=1;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if((i>>j)&1){
                for(int k=0;k<n;k++){
                    if(!((i>>k)&1)){
                        f[i|(1<<k)][k]=min(f[i|(1<<k)][k],f[i][j]+a[j][k]);
                    }
                }
            }
        }
    }
    int ans=inf;
    for(int i=0;i<n;i++){
        ans=min(ans,f[(1<<n)-1][i]);
    }
    cout<<ans<<endl;
}