bzoj 1097 [POI2007]旅游景点atr（最短路，状压DP）

【题意】

给定一个n点m边的无向图，要求1开始n结束而且顺序经过k个点，给出经过关系x,y代表y必须在x之后经过，求最短路。

【思路】

先对k个点进行spfa求出最短路。

设f[s][i]代表经过点集为s且目前处于i，则有转移式：

f[s][i]<-f[s|(1<<j)][j]，s必须包含需要在j之前经过的所有点

用a[i]表示需要在在经过i之前经过的所有点集，即可完成判断。

【代码】

 1 #include<set>
 2 #include<cmath>
 3 #include<queue>
 4 #include<vector>
 5 #include<cstdio>
 6 #include<cstring>
 7 #include<iostream>
 8 #include<algorithm>
 9 #define trav(u,i) for(int i=front[u];i;i=e[i].nxt)
10 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)
11 using namespace std;
12 
13 typedef long long ll;
14 const int N = 5e4+10; 
15 const int M = 5e5+10;
16 const int NK = 22;
17 const int inf = 2e9;
18 
19 ll read() {
20     char c=getchar();
21     ll f=1,x=0;
22     while(!isdigit(c)) {
23         if(c=='-') f=-1; c=getchar();
24     }
25     while(isdigit(c))
26         x=x*10+c-'0',c=getchar();
27     return x*f;
28 }
29 
30 struct Edge {
31     int v,w,nxt;
32 }e[M];
33 int en=1,front[N];
34 void adde(int u,int v,int w) 
35 {
36     e[++en]=(Edge){v,w,front[u]}; front[u]=en;
37 }
38 
39 int n,m,K,bin[NK];
40 int f[1<<NK][NK];
41 int dis[NK][N],a[N];
42 queue<int> q; int inq[N];
43 
44 
45 void spfa(int s) {
46     memset(inq,0,sizeof(inq));
47     FOR(i,0,n) dis[s][i]=inf;
48     q.push(s); inq[s]=1; dis[s][s]=0;
49     while(!q.empty()) {
50         int u=q.front(); q.pop(); inq[u]=0;
51         trav(u,i) {
52             int v=e[i].v;
53             if(dis[s][v]>dis[s][u]+e[i].w) {
54                 dis[s][v]=dis[s][u]+e[i].w;
55                 if(!inq[v])
56                     inq[v]=1,q.push(v);
57             }
58         }
59     }
60 }
61 
62 int dp(int now,int u) {
63     int& ans=f[now][u];
64     if(ans>=0) return ans;
65     if(now==bin[K]-1) return dis[u][n-1]; 
66     ans=inf;
67     FOR(i,1,K)
68         if((now&a[i])==a[i])
69             ans=min(ans,dp(now|bin[i-1],i)+dis[u][i]);
70     return ans;  
71 }
72 
73 int main()
74 {
75     //freopen("in.in","r",stdin);
76     //freopen("out.out","w",stdout);
77     bin[0]=1;
78     FOR(i,1,NK-1) bin[i]=bin[i-1]<<1;
79     n=read(),m=read(),K=read();
80     FOR(i,1,m) {
81         int u=read(),v=read(),w=read();
82         u--,v--;
83         adde(u,v,w),adde(v,u,w);
84     }
85     FOR(i,0,K) spfa(i);
86     int x=read();
87     while(x--) {
88         int u=read(),v=read();
89         a[v-1]|=bin[u-2];
90     }
91     memset(f,-1,sizeof(f));
92     printf("%d",dp(0,0));
93     return 0;
94 }