POJ4124偉大的航線

我是要成為海賊王的男人！”，路飛一邊喊着這樣的口号，一邊和他的夥伴們一起踏上了偉大航路的艱險曆程。

路飛他們偉大航路行程的起點是羅格鎮，終點是拉夫德魯（那裡藏匿着“唯一的大秘寶”——ONE PIECE）。而航程中間，則是各式各樣的島嶼。

因為偉大航路上的氣候十分異常，是以來往任意兩個島嶼之間的時間差别很大，從A島到B島可能需要1天，而從B島到A島則可能需要1年。當然，任意兩個島之間的航行時間雖然差别很大，但都是已知的。

現在假設路飛一行從羅格鎮（起點）出發，周遊偉大航路中間所有的島嶼（但是已經經過的島嶼不能再次經過），最後到達拉夫德魯（終點）。假設他們在島上不作任何的停留，請問，他們最少需要花費多少時間才能到達終點？

輸入

輸入資料包含多行。

第一行包含一個整數N(2 < N ≤ 16)，代表偉大航路上一共有N個島嶼（包含起點的羅格鎮和終點的拉夫德魯）。其中，起點的編号為1，終點的編号為N。

之後的N行每一行包含N個整數，其中，第i(1 ≤ i ≤ N)行的第j(1 ≤ j ≤ N)個整數代表從第i個島嶼出發到第j個島嶼需要的時間t(0 < t < 10000)。第i行第i個整數為0。

輸出

輸出為一個整數，代表路飛一行從起點周遊所有中間島嶼（不重複）之後到達終點所需要的最少的時間。

樣例輸入

樣例輸入1：

4

0 10 20 999

5 0 90 30

99 50 0 10

999 1 2 0

樣例輸入2：

5

0 18 13 98 8

89 0 45 78 43

22 38 0 96 12

68 19 29 0 52

95 83 21 24 0

樣例輸出

樣例輸出1：

100

樣例輸出2：

137

提示

提示：

對于樣例輸入1：路飛選擇從起點島嶼1出發，依次經過島嶼3，島嶼2，最後到達終點島嶼4。花費時間為20+50+30=100。

對于樣例輸入2：可能的路徑及總時間為：

1,2,3,4,5: 18+45+96+52=211

1,2,4,3,5: 18+78+29+12=137

1,3,2,4,5: 13+38+78+52=181

1,3,4,2,5: 13+96+19+43=171

1,4,2,3,5: 98+19+45+12=174

1,4,3,2,5: 98+29+38+43=208

是以最短的時間花費為137

單純的枚舉在N=16時需要14!次運算，一定會逾時。

本人的心得感悟：

這道題需要很明顯用到DFS深度搜尋，經過的點數為N，如果單純用DFS的話，需要搜尋(N-1)!次，妥妥逾時，這時我們需要對這棵龐大的搜尋樹進行剪枝。我們引入一個狀态矩陣。存放到達該路徑下到達目前點的目前最優值。咳咳，例如：從1點出發，到達5點，那麼zhuang_tai[5][11101]代表三條可能的路徑：1->2->3->4->5,1->3->2->4->5,1->2->4->3->5,1->3->2->5->4,1->4->2->3->5,1->4->3->2->5這6條路徑，如果不進行剪枝的話，5點之後的搜尋灰常龐大！！！是以當zhuang_tai[5][11101] < 目前值time時，{return;}減掉，不再5點之後繼續深度搜尋，這是其中一處剪枝，受益匪淺！

#include<iostream>
#include<string.h>
#include<algorithm>
using namespace std;
int reach_time[20][20];
int zhuang_tai[20][1<<20];
int visited[20];
int N;
int ans ;//存放周遊所有點的路徑的目前最少時間，即完整便利路徑的目前最優值
/*
BFS函數說明：深度優先搜尋，cur_land代表目前通路節點的标号
time代表通路到cur_land節點已經用的時間
total:已經通路到的點（包括起點和終點）的個數
land_state:目前路徑的狀态
*/
void BFS(int cur_land,int time,int total,int land_state)
{
    if(time >= ans){return ;}//到達cur_land點時用的時間已經大于目前最優值了，剪枝（你好沒走完呢，用的時間比全路程時間還多，妥妥剪枝）
    if(zhuang_tai[cur_land][land_state] == -1 ||zhuang_tai[cur_land][land_state] > time)//zhuang_tai矩陣如果是新的，直接寫入，如果有其他更優的路徑，更新
    {
        zhuang_tai[cur_land][land_state] = time;
    }
    else{return ;}//目前路徑的time大于以前的時間，剪枝
    if(total == N && cur_land == N)//total == n說明這個路徑已經周遊到所有點；cur_land == n說明最後一個點是N點
    {
        ans = min(ans,time);//更新目前最優值
        return ;
    }
    for(int i = 2;i <= N;i ++ )
    {
        if(visited[i]){continue;}//在這條路徑下，标号為i的點被通路過，換其他的點
        else//在這條路徑下，i點沒有被通路
        {
            visited[i] = 1;//置通路标志
            BFS(i,time + reach_time[cur_land][i],total + 1,land_state + (1 << i));
            //cout<<"cur_land"<<cur_land<<endl;
            visited[i] = 0;
        }
    }
}
int main()
{

    while(cin >> N)
    {
       memset(zhuang_tai,-1,sizeof(zhuang_tai));//将狀态矩陣初始化-1
       memset(visited,0,sizeof(visited));//将通路矩陣置0
       ans = 0x3fffffff;//更新最優值ans
       for(int i = 1;i <= N;i ++ )//節點标号是從1到N
       {
           for(int j = 1;j <= N;j ++)//節點标号是從1到N
           {
               cin >> reach_time[i][j];
           }
       }
       BFS(1,0,1,1);
       cout<<ans<<endl;
    }
    return 0;
}