解题思路：

利用深度优先搜索找到经历1到n-1的路径然后再从n-1到n，结合最优性剪枝。

如果当前已经找到的最优路径时间为T，那么以后总时间已经大于T的走法就可以直接放弃。

如果之前到达某个状态比这次花费的时间要少，则剪枝。

如何表示某个状态呢，该状态可以去掉1和n，只与当前所在城市和走过的城市有关，那么可以设城市2为2^0，城市3为2^1……

就可以用zta[14][1<<14]表示到达该点且同时经过某些点时所用的最少时间。

1 #include 
     
       2 #include 
      
        3 using namespace std; 4 const int inf = 0x3f3f3f3f; 5 int n; 6 int timeList[20][20]; 7 int ans; 8 int totaltime; 9 bool visited[20];10 int zta[14][1<<14];11 int zt;12 int pow2[20];13 int all;14 void dfs(int s)15 {16     if(zt==all)17     {18         int t=totaltime+timeList[s][n];19         if(t
       
        = ans)28             continue;29         if(zta[i-2][zt+pow2[i-2]] <= totaltime+timeList[s][i])30             continue;31         visited[i]=1;32         totaltime+=timeList[s][i];33         zt+=pow2[i-2];34         zta[i-2][zt]=totaltime;35         dfs(i);36         visited[i]=0;37         totaltime-=timeList[s][i];38         zt-=pow2[i-2];39     }40 }41 void init()42 {43     ans=inf;44     memset(visited,0,sizeof(visited));45     visited[1]=1;46     memset(zta,inf,sizeof(zta));47     zt=0;48     for(int i=0; i<14; i++)49         pow2[i]=(1<
        
         >n;59     for(int i=1; i<=n; i++)60         for(int j=1; j<=n; j++)61             cin>>timeList[i][j];62     init();63     dfs(1);64     cout<
         
          <