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; }
