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,总长度为1 9。注意FGD为了从城市2到城市4可以路过城市3,但不在城市3停留。这样就不违反FGD的要求了。并且由于FGD想要 走最短的路径，因此这个方案正是FGD需要的。 Input
第一行包含3个整数N(2<=N<=20000),M(1<=M<=200000),K(0<=K<=20),意义如上所述。 Output
只包含一行，包含一个整数，表示最短的旅行距离。 Sample Input 8 15 4
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 19
HINT
上面对应于题目中给出的例子。
解题思路： 首先预处理一下K+1个点间的最短路，这个可以堆优化Dij，或者SPFA，然后状压DP，那么如何DP？这个如果状压DP做的比较多还是很容易YY出来的，DP[i][j]代表当前状态是i,停留在第j个城市的走的最短距离。。那么转移就很好搞了。 dp[i][j]=min(dp[i][j],dp[k][x]+dis[x][i]) 其中， k代表和状态i不冲突的状态，x代表k状态下停留在x的最短距离，那么dis[x][i]是x到i的最短路，这个已经预处理出来了，那么这个DP的复杂度是多少呢？ O(2^k * k * k) 然后加上预处理最短路的时间，就是O(2^k*k*k + k*logk)，就可以通过这个题了， 为了加速我还加了一个读入外挂。。具体细节见代码
#include <bits/stdc++.h>using namespace std;typedef long long LL;struct FastIO{ static const int S = 1310720; int wpos; char wbuf[S]; FastIO() : wpos(0) {} inline int xchar() { static char buf[S]; static int len = 0, pos = 0; if (pos == len) pos = 0, len = fread(buf, 1, S, stdin); if (pos == len) return -1; return buf[pos ++]; } inline int xuint() { int c = xchar(), x = 0; while (c <= 32) c = xchar(); for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0'; return x; } inline int xint() { int s = 1, c = xchar(), x = 0; while (c <= 32) c = xchar(); if (c == '-') s = -1, c = xchar(); for (; '0' <= c && c <= '9'; c = xchar()) x = x * 10 + c - '0'; return x * s; } inline void xstring(char *s) { int c = xchar(); while (c <= 32) c = xchar(); for (; c > 32; c = xchar()) * s++ = c; *s = 0; } inline void wchar(int x) { if (wpos == S) fwrite(wbuf, 1, S, stdout), wpos = 0; wbuf[wpos ++] = x; } inline void wint(LL x) { if (x < 0) wchar('-'), x = -x; char s[24]; int n = 0; while (x || !n) s[n ++] = '0' + x % 10, x /= 10; while (n--) wchar(s[n]); } inline void wstring(const char *s) { while (*s) wchar(*s++); } ~FastIO() { if (wpos) fwrite(wbuf, 1, wpos, stdout), wpos = 0; }} io;const int maxn = 40005;const int inf = 1e9;int n, m, q, K, edgecnt, mask;int bin[22], a[22], dis[22][22], head[maxn], d[maxn], dp[1048576][22], vis[maxn]; //dp[i][j]表示的是，状态为i，最后停留在j的最小的走的距离struct node{int v, w, nxt; } E[400005];void init(){ bin[0] = 1; for(int i = 1; i < 22; i++) bin[i] = bin[i-1] << 1; memset(dp, -1, sizeof(dp)); memset(head, -1, sizeof(head)); edgecnt = 0;}void addedge(int u, int v, int w){ E[edgecnt].v = v, E[edgecnt].w = w, E[edgecnt].nxt = head[u], head[u] = edgecnt++;}void dij(int x){ //预处理k个点的最短路 PRiority_queue <pair <int, int>, vector <pair <int, int> > , greater <pair <int, int> > > q; for(int i = 1; i <= n; i++){ vis[i] = 0; d[i] = inf; } d[x] = 0; q.push(make_pair(0, x)); while(!q.empty()){ int u = q.top().second; q.pop(); if(vis[u]) continue; vis[u] = 1; for(int i = head[u]; ~i; i = E[i].nxt){ int v = E[i].v; if(d[u] + E[i].w < d[v]){ d[v] = d[u] + E[i].w; q.push(make_pair(d[v], v)); } } } for(int i = 1; i <= K + 1; i++) dis[x][i] = d[i]; dis[x][0] = d[n];}int main(){ init(); //scanf("%d%d%d", &n, &m, &K); n = io.xint(), m = io.xint(), K = io.xint(); mask = bin[K] - 1; for(int i = 1; i <= m; i++){ int u, v, w; //scanf("%d%d%d", &u, &v, &w); u = io.xint(), v = io.xint(), w = io.xint(); addedge(u, v, w); addedge(v, u, w); } for(int i = 1; i <= K + 1; i++) dij(i); //scanf("%d", &q); q = io.xint(); //筛选有效状态 for(int i = 1; i <= q; i++){ int u, v; //scanf("%d%d", &u, &v); u = io.xint(), v = io.xint(); a[v] += bin[u - 2]; } dp[0][1] = 0; for(int st = 0; st <= mask; st++){ for(int x = 1; x <= K + 1; x++){ if(dp[st][x] != -1){ for(int i = 2; i <= K + 1; i++){ int en = (st | (bin[i - 2])); if((st & a[i]) == a[i]){ //转移的限制条件 if(dp[en][i] > dp[st][x] + dis[x][i] || dp[en][i] == -1){ dp[en][i] = dp[st][x] + dis[x][i]; } } } } } } int ans = inf; for(int i = 1; i <= K + 1; i++){ if(dp[mask][i] == -1) continue; //不合法的状态不能比较 ans = min(ans, dp[mask][i] + dis[i][0]); } printf("%d/n", ans); return 0; }
