郊区春游（状压DP水题）

题目链接：

https://ac.nowcoder.com/acm/problem/16122

题目大意：

中文

具体思路：

首先对全图跑一遍floyed，然后dp[i][j]表示第i个状态在j点停下来的最短距离。

AC代码：

1 #include
2 using namespace std;
3 #define ll long long
4 #define inf 0x3f3f3f3f
5 #define LL_inf (1ll <<60)
6 const int maxn = 200+55;
7 const int mod = 1e9 + 7;
8 int sto[maxn];
9 int dp[34000][maxn];
10 int dis[maxn][maxn];
11 int n,m,r;
12 void floyed()
13 {
14 for(int i=1; i<=n; i++)
15 {
16 for(int j=1; j<=n; j++)
17 {
18 for(int k=1; k<= n; k++)
19 {
20 dis[j][k]=min(dis[j][k],dis[j][i]+dis[i][k]);
21 }
22 }
23 }
24 }
25 int main()
26 {
27 // cout<<(1<<15)<28 scanf("%d %d %d",&n,&m,&r);
29 for(int i=0; i30 {
31 scanf("%d",&sto[i]);
32 }
33 for(int i=1; i<=n; i++)
34 {
35 for(int j=1; j<=n; j++)
36 {
37 if(i==j)
38 dis[i][j]=0;
39 else
40 dis[i][j]=inf ;
41 }
42 }
43 int st,ed,val;
44 for(int i=1; i<=m; i++)
45 {
46 scanf("%d %d %d",&st,&ed,&val);
47 //st--,ed--;
48 dis[st][ed]=min(dis[st][ed],val);
49 dis[ed][st]=dis[st][ed];
50 }
51 floyed();
52 // for(int i=0;i53 // for(int j=i;j54 // cout<55 // }
56 // }
57 memset(dp,inf,sizeof (dp) );
58 for(int i=0; i59 {
60 dp[(1<61 }
62 int maxstate=(1<63 for(int i=0; i<=maxstate; i++)
64 {
65 for(int j=0; j66 {
67 if((i&(1<68 continue;
69 for(int k=0; k70 {
71 // if(i&(1<72 // continue;
73 dp[i^(1<74 }
75 }
76 }
77 int minn=inf ;
78 for(int i=0; i79 {
80 minn=min(minn,dp[maxstate][i]);
81 }
82 printf("%d\n",minn);
83 return 0;
84 }