题意：给出一个简单带权无向图和起止点，以及若干张马车车票，每张车票可以雇到相应数量的马。
点 u, v 间有边时，从 u 到 v 或从 v 到 u 必须用且仅用一张车票，花费的时间为 w(u, v) / ticket[i]，
其中 w(u, v) 表示边的权值，ticket[i] 表示第 i 张车票可以雇到的马匹数。求从起点到终点花费的最小时间。

如果不能到达终点，输出“Impossible”。（点数 <= 30，票数 <= 8）*/ 

 

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;const double INF=10000000000.0;const int MAX_N=8;const int MAX_M=30;double weight[MAX_M][MAX_M];double ticket[MAX_N];int n,m,p,a,b;double dp[1<
         
          =0){ // 使用车票i 从 k 移动到 v dp[i|(1<
          
           <
           
            >n>>m>>p>>a>>b){ if(n+m+p+a+b==0)break; for(int i=0;i
            
             >ticket[i]; memset(weight,-1,sizeof(weight)); // -1表示没有边 for(int i=0;i
             
              >x>>y>>z; x--;y--; weight[x][y]=z; weight[y][x]=z; } solve(); } return 0;}