有m座城市，n张车票，p条路。然后每张车票有一个速度值。我们每次通过一条路都需要一张车票，花费时间为路径长度比上所选车票的速度值。问从起点a到终点b的最短时间花费。M不超过30，n不超过10。
我们显然不能求一条最短路，再依次对最短路上的每条边用最合适的车票。考虑一种情况，第一条边很长，其他边很短。那如果第一条边用了一张速度很快的车票，那么最终的路径长度反而会很优秀。所以这道题不能直接进行最短路。我们发现n只有10，考虑状压DP。用dp[sta][u]表示在城市u，车票使用情况为sta的最小时间花费。又因为二进制状态转移顺序不明显，所以我们采用记忆化搜索。每次检索sta中哪张车票用过了，我们在枚举是从哪个城市用了这张车票过来，然后用那个城市来更新当前城市的答案。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 using namespace std; 5 typedef long long ll; 6 const double inf = 10000000000.0; 7 const int MAXM = 40,MAXN = 15; 8 int n,m,p,a,b,t[MAXN]; 9 int d[MAXM][MAXM]; 10 double dp[1 << MAXN][MAXM]; 11 double dfs(int sta,int u) 12 { 13 if (dp[sta][u] >= 0.0) 14 return dp[sta][u]; 15 dp[sta][u] = inf; 16 for (int v = 1;v <= m;v++) 17 for (int i = 1;i <= n;i++) 18 if (((sta >> (i - 1)) & 1) == 0) 19 if(d[v][u] >= 0) 20 dp[sta][u] = min(dp[sta][u],dfs(sta | (1 << (i - 1)),v) + (double)d[v][u] / t[i]); 21 return dp[sta][u]; 22 } 23 int main() 24 { 25 for(;;) 26 { 27 scanf("%d%d%d%d%d",&n,&m,&p,&a,&b); 28 if (n == 0) 29 break; 30 for (int i = 1;i <= n;i++) 31 scanf("%d",&t[i]); 32 memset(d,-1,sizeof(d)); 33 int tx,ty,tz; 34 for (int i = 1;i <= p;i++) 35 { 36 scanf("%d%d%d",&tx,&ty,&tz); 37 d[tx][ty] = tz; 38 d[ty][tx] = tz; 39 } 40 for (int i = 0;i < 1 << n;i++) 41 for (int j = 1;j <= m;j++) 42 dp[i][j] = -1.0; 43 double res = inf; 44 dp[(1 << n) - 1][a] = 0.0; 45 for (int i = 0;i < (1 << n);i++) 46 res = min(res,dfs(i,b)); 47 if (res == inf) 48 printf("Impossible "); 49 else 50 printf("%.3f ",res); 51 } 52 53 return 0; 54 }