Description
FGD想从成都去上海旅游。在旅途中他希望经过一些城市并在那里欣赏风景，品尝风味小吃或者做其他的有趣的事情。经过这些城市的顺序不是完全随意的，比如说FGD不希望在刚吃过一顿大餐之后立刻去下一个城市登山，而是希望去另外什么地方喝下午茶。幸运的是,FGD的旅程不是既定的，他可以在某些旅行方案之间进行选择。由于FGD非常讨厌乘车的颠簸，他希望在满足他的要求的情况下，旅行的距离尽量短，这样他就有足够的精力来欣赏风景或者是泡MM了^_^. 整个城市交通网络包含N个城市以及城市与城市之间的双向道路M条。城市自1至N依次编号，道路亦然。没有从某个城市直接到它自己的道路，两个城市之间最多只有一条道路直接相连，但可以有多条连接两个城市的路径。任意两条道路如果相遇，则相遇点也必然是这N个城市之一，在中途，由于修建了立交桥和下穿隧道，道路是不会相交的。每条道路都有一个固定长度。在中途，FGD想要经过K(K<=N-2)个城市。成都编号为1，上海编号为N,而FGD想要经过的N个城市编号依次为2,3,…,K+1. 举例来说，假设交通网络如下图。FGD想要经过城市2,3,4,5，并且在2停留的时候在3之前，而在4,5停留的时候在3之后。那么最短的旅行方案是1-2-4-3-4-5-8,总长度为19。注意FGD为了从城市2到城市4可以路过城市3,但不在城市3停留。这样就不违反FGD的要求了。并且由于FGD想要走最短的路径，因此这个方案正是FGD需要的。
Input
第一行包含3个整数N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20),意义如上所述。以下M行，每行包含3个整数X，Y，Z，(1<=X
Output
只包含一行，包含一个整数，表示最短的旅行距离。
Sample Input
1 2 3
1 3 4
1 4 4
1 6 2
1 7 3
2 3 6
2 4 2
2 5 2
3 4 3
3 6 3
3 8 6
4 5 2
4 8 6
5 7 4
5 8 6
3
2 3
3 4
3 5
Sample Output
先跑k次最短路找出前k个点两两之间的最短路径，将这些路径缩成边，然后在k个点上做状压DP。
常数跪QAQ，压着时间过ORZ
代码：
1 #include <cstdio> 2 #include <cstring> 3 #define maxn 20010 4 #define maxm 400010 5 int t[maxm], p[maxm], w[maxm], la[maxn], e; 6 int n, m, k, l, a, b, c, lim[1 << 21]; 7 int dis[23][maxn], dp[23][1 << 21], end; 8 int q[maxm * 10], h, r, v[maxn], no; 9 inline void ins (int from, int to, int weight) 10 { 11 e++; 12 p[e] = la[from]; 13 t[e] = to; 14 w[e] = weight; 15 la[from] = e; 16 } 17 inline int min (int a, int b) 18 { 19 return a < b ? a : b; 20 } 21 void spfa (int s) 22 { 23 memset (v, 0, sizeof (v)); 24 h = r = 0; 25 q[0] = s; 26 dis[s][s] = 0; 27 while (h <= r) 28 { 29 v[no = q[h]] = 0; 30 for (int i = la[no]; i; i = p[i]) 31 { 32 if (dis[s][t[i]] > dis[s][no] + w[i]) 33 { 34 dis[s][t[i]] = dis[s][no] + w[i]; 35 if (!v[t[i]]) v[q[++r] = t[i]] = 1; 36 } 37 } 38 h++; 39 } 40 dis[s][k + 2] = dis[s][n]; 41 } 42 int dfs (int i, int st) 43 { 44 if (dp[i][st] >= 0) return dp[i][st]; 45 if (st == end) return dp[i][st] = dis[i][k + 2]; 46 dp[i][st] = 1000000000; 47 for (int j = k + 1; j > 1; j--) 48 if ((st & lim[j]) == lim[j]) 49 dp[i][st] = min (dis[i][j] + dfs (j, st | (1 << (j - 2))), dp[i][st]); 50 return dp[i][st]; 51 } 52 int main () 53 { 54 memset (dis, 63, sizeof (dis)); 55 memset (dp, -1, sizeof (dp)); 56 scanf ("%d %d %d", &n, &m, &k); 57 end = (1 << k) - 1; e = 0; 58 for (int i = 0; i < m; i++) 59 scanf ("%d %d %d", &a, &b, &c), 60 ins (a, b, c), ins (b, a, c); 61 for (int i = k + 1; i; i--) 62 spfa (i); 63 scanf ("%d", &l); 64 for (int i = 0; i < l; i++) 65 scanf ("%d %d", &a, &b), 66 lim[b] |= 1 << (a - 2); 67 printf ("%d", dfs (1, 0)); 68 }