題意：
? ? ? 給你一個(gè)地圖，問你吧所有的隧道都走完的最小費(fèi)用，起點(diǎn)不固定，穿越隧道的時(shí)間不計(jì)，在隧道外邊每移動一步花費(fèi)一秒。

思路：
? ? ? 先bfs求出所有dis[i][j]（i的終點(diǎn)和j的起點(diǎn)的距離），然后在dp[i][j]，i表示當(dāng)
前狀態(tài)（二進(jìn)制壓縮后的狀態(tài)）j表示第幾個(gè)點(diǎn)，則更新的方程也很簡單
dp[i|(1<<(k-1))][j] = minn(本身,dp[i][j] + dis[j][k]);記得要加一個(gè)if((i|(1<<(k-1))) == 0)我個(gè)人認(rèn)為沒必要加，結(jié)果不加就wa，現(xiàn)在還在研究中，記得這種題目之前

做過很多，但之前的數(shù)據(jù)都很小，可以直接n!,寫個(gè)搜索或者全排列暴力枚舉過去，今天的這個(gè)過不去只能用dp了，之前沒想過dp因?yàn)樽约篸p很水，想題很少會往dp上想，以后要加強(qiáng)了.

#include<stdio.h> #include<string.h> #include<queue>#define INF 1000000000 using namespace std;typedef struct {int sx ,sy ,ex ,ey; }SD;typedef struct {int x, y ,t; }NODE;SD sd[18]; NODE xin ,tou; int dis[18][18]; char map[18][18]; int mark[18][18]; int dp[(1<<15)+10][18]; int dir[4][2] = {0 ,1 ,0 ,-1 ,1 ,0 ,-1 ,0};bool ok(NODE a ,int n) {return a.x >= 1 && a.x <= n && a.y >= 1 && a.y <= n && !mark[a.x][a.y] && map[a.x][a.y] == '.'; }int minn(int x ,int y) {return x < y ? x : y; }int bfs(int sx ,int sy ,int ex ,int ey ,int n) {memset(mark ,0 ,sizeof(mark));xin.x = sx ,xin.y = sy ,xin.t = 0;mark[sx][sy] = 1;queue<NODE>q;q.push(xin);while(!q.empty()) {tou = q.front();q.pop();if(tou.x == ex && tou.y == ey)return tou.t;for(int i = 0 ;i < 4 ;i ++){xin.x = tou.x + dir[i][0];xin.y = tou.y + dir[i][1];xin.t = tou.t + 1;if(ok(xin ,n)){mark[xin.x][xin.y] = 1;q.push(xin);}}}return INF; }int main () {int n ,m ,i ,j ,k;while(~scanf("%d %d" ,&n ,&m)){getchar();for(i = 1 ;i <= n ;i ++){for(j = 1 ;j <= n ;j ++)scanf("%c" ,&map[i][j]);getchar();}for(i = 1 ;i <= m ;i ++){scanf("%d %d %d %d" ,&sd[i].sx ,&sd[i].sy ,&sd[i].ex ,&sd[i].ey);for(j = i ;j <= m ;j ++)dis[i][j] = dis[j][i] = INF;}for(i = 1 ;i <= m ;i ++)for(j = i ;j <= m ;j ++){if(i == j) {dis[i][j] = 0;continue;}dis[i][j] = bfs(sd[i].ex ,sd[i].ey ,sd[j].sx ,sd[j].sy ,n);dis[j][i] = bfs(sd[j].ex ,sd[j].ey ,sd[i].sx ,sd[i].sy ,n);}for(i = 0 ;i <= (1 << m) ;i ++)for(j = 0 ;j <= m ;j ++)dp[i][j] = INF;for(i = 1 ;i <= m ;i ++)dp[1 << (i - 1)][i] = 0;for(i = 0 ;i < (1 << m) ;i ++)for(j = 1 ;j <= m ;j ++)//if(dp[i][j] != INF) for(k = 1 ;k <= m ;k ++)if(!(i & (1 << (k - 1))))//***** dp[i|(1<<(k-1))][k] = minn(dp[i|(1<<(k-1))][k] ,dp[i][j] + dis[j][k]);int ans = INF;for(i = 1 ;i <= m ;i ++)ans = minn(ans ,dp[(1<<m) - 1][i]);ans == INF ? puts("-1") : printf("%d\n" ,ans); }return 0; }

總結(jié)

以上是生活随笔為你收集整理的bfs+状态压缩dp的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。