HDU 4568 SPFA + TSP

這道題是長沙邀請賽的題，當時是道簽到題。

這種題還是很常見的，講一下思路。

首先是預處理出每個寶藏之間的距離，還有到邊的距離，直接對每個寶藏進行一次SPFA就可以了。

然後就是經典的求TSP的過程。

#include <set>   
#include <map>   
#include <stack>   
#include <cmath>   
#include <queue>   
#include <cstdio>   
#include <string>   
#include <vector>   
#include <iomanip>   
#include <cstring>   
#include <iostream>   
#include <algorithm>   
#define Max 2505   
#define FI first   
#define SE second   
#define ll long long   
#define PI acos(-1.0)   
#define inf 1111111111   
#define LL(x) ( x << 1 )   
#define bug puts("here")   
#define PII pair<int,int>   
#define RR(x) ( x << 1 | 1 )   
#define mp(a,b) make_pair(a,b)   
#define mem(a,b) memset(a,b,sizeof(a))   
#define infA(a) for (int i = 0 ; i <= n ; ++ i)a[i] = inf ;   
#define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i )   
  
  
using namespace std;  
  
inline void RD(int &ret) {  
    char c;  
    do {  
        c = getchar();  
    } while(c < '0' || c > '9') ;  
    ret = c - '0';  
    while((c=getchar()) >= '0' && c <= '9')  
        ret = ret * 10 + ( c - '0' );  
}  
  
inline void OT(int a) {  
    if(a >= 10)OT(a / 10) ;  
    putchar(a % 10 + '0') ;  
}  
#define N 222   
#define K 15   
  
  
int Map[N][N] ;  
struct tru {  
    int x ,y ;  
} tk[K] ;  
int tt ;  
int MM[K][K] ;  
int dp[1 << K][K] ;  
int dis[N][N] ;  
bool vis[N][N] ;  
PII qe[1111111] ;  
int D[K] ;  
int n , m ;  
int mx[4] = {0 , 0 , 1 , -1} ;  
int my[4] = {1 , -1 , 0 , 0} ;  
int inmap(int x ,int y) {  
    if(x >= 0 && x < n && y >= 0 && y < m && Map[x][y] != -1)return 1 ;  
    return 0 ;  
}  
void init(int pos) {  
    for (int i = 0 ; i < n ; i ++ ) {  
        for (int j = 0 ; j < m ; j ++ ) {  
            dis[i][j] = inf ;  
            vis[i][j] = 0 ;  
        }  
    }  
    dis[tk[pos].x][tk[pos].y] = Map[tk[pos].x][tk[pos].y] == -1 ? inf : 0 ;  
    int h = 0 , t = 0 ;  
    qe[h ++ ] = mp(tk[pos].x ,tk[pos].y) ;  
    while(h > t) {  
        PII tp = qe[t ++ ] ;  
        vis[tp.FI][tp.SE] = 0 ;  
        if(tp.FI == 0 || tp.FI == n - 1 || tp.SE == 0 || tp.SE == m - 1) {  
            D[pos] = min(D[pos] , dis[tp.FI][tp.SE]) ;  
        }  
        for (int i = 0 ; i < 4 ; i ++ ) {  
            int tx = tp.FI + mx[i] ;  
            int ty = tp.SE + my[i] ;  
            if(inmap(tx , ty)) {  
                if(dis[tx][ty] > dis[tp.FI][tp.SE] + Map[tx][ty]) {  
                    dis[tx][ty] = dis[tp.FI][tp.SE] + Map[tx][ty] ;  
                    if(!vis[tx][ty]) {  
                        vis[tx][ty] = 1 ;  
                        qe[h ++ ] = mp(tx ,ty) ;  
                    }  
                }  
            }  
        }  
    }  
}  
  
  
int main() {  
#ifndef ONLINE_JUDGE   
    freopen("in.txt","r",stdin) ;  
    freopen("out.txt","w",stdout) ;  
#endif   
    int T ;  
    cin >> T ;  
    while ( T -- ) {  
        cin >> n >> m ;  
        REP(i , 0, n - 1 ) {  
            REP(j , 0 , m - 1)scanf("%d",&Map[i][j]) ;  
        }  
        cin >> tt ;  
        REP(i , 0 , tt - 1) {  
            RD(tk[i].x) ;  
            RD(tk[i].y) ;  
        }  
        REP(i , 0 , tt - 1) {  
            REP(j , 0 , tt - 1) {  
                MM[i][j] = inf ;  
            }  
            MM[i][i] = 0 ;  
            D[i] = inf ;  
        }  
        for (int i = 0 ; i < (1 << tt) ; i ++ ) {  
            for (int j = 0 ; j < tt ; j ++ )dp[i][j] = inf ;  
        }  
  
        REP(i , 0 , tt - 1) {  
            init(i) ;  
            REP(j , 0 , tt - 1) {  
                if(i == j)continue ;  
                MM[i][j] = min(MM[i][j] , dis[tk[j].x][tk[j].y]) ;//寶藏到寶藏之間的最近距離   
            }  
            dp[1 << i][i] = D[i] + Map[tk[i].x][tk[i].y] ;//該寶藏到達邊的最近距離   
        }  
        for (int i = 0 ; i < 1 << tt ; i ++ ) {  
            for (int j = 0 ; j < tt ; j ++ ) {  
                if(i & (1 << j) == 0)continue ;  
                if(dp[i][j] == inf)continue ;  
                for (int k = 0 ; k < tt ; k ++ ) {  
                    if(i & (1 << k))continue ;  
                    int tp = i | (1 << k) ;  
                    dp[tp][k] = min(dp[tp][k] , dp[i][j] + MM[j][k]) ;  
                }  
            }  
        }  
        int ans = inf ;  
        for (int i = 0 ; i < tt ; i ++ ) {  
            ans = min(ans , dp[(1 << tt) - 1][i] + D[i] ) ;  
        }  
        cout << ans << endl;  
    }  
    return 0 ;  
}  
/* 
5 
4 4 
3 3 3 3 
3 -1 -1 -1 
3 -1 3 3 
3 -1 -1 -1 
1 
2 2 
 
5 5 
1 1 1 1 1 
1 -1 -1 -1 -1 
1 -1 -1 -1 -1 
1 -1 -1 -1 -1 
1 -1 -1 -1 -1 
2 
4 0 
0 4 
 
3 3 
3 2 3 
5 4 3 
1 4 2 
1 
1 1 
3 3 
3 2 3 
5 4 3 
1 4 2 
2 
1 1 
2 2 
 
*/