dp[s][v] 从源点到达 v，状态为s,v的最小值。 for循环枚举就行了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <string> 7 #include <vector> 8 #include <set> 9 #include <map> 10 #include <stack> 11 #include <queue> 12 #include <sstream> 13 #include <iomanip> 14 using namespace std; 15 typedef long long LL; 16 const double INF=0x4fffffff; 17 const double EXP=1e-5; 18 const int MS=10; 19 const int SIZE=31; 20 21 double dp[1<<MS][SIZE]; 22 23 int edges[SIZE][SIZE]; 24 int cnt[MS]; 25 26 int start,final,tickets,citys,edge; 27 28 void solve() 29 { 30 for(int i=0;i<(1<<tickets);i++) 31 fill(dp[i],dp[i]+SIZE,INF); 32 dp[(1<<tickets)-1][start-1]=0; 33 double res=INF; 34 for(int i=(1<<tickets)-1;i>=0;i--) 35 { 36 res=min(res,dp[i][final-1]); 37 for(int u=0;u<citys;u++) 38 { 39 for(int j=0;j<tickets;j++) 40 { 41 if((i>>j)&1) 42 { 43 for(int v=0;v<citys;v++) 44 if(edges[u][v]>=0) 45 dp[i-(1<<j)][v]=min(dp[i-(1<<j)][v],dp[i][u]+double(edges[u][v])/cnt[j]); 46 } 47 } 48 } 49 } 50 if(res+EXP>=INF) 51 printf("Impossible "); 52 else 53 printf("%.3lf ",res); 54 } 55 56 int main() 57 { 58 while(scanf("%d%d%d%d%d",&tickets,&citys,&edge,&start,&final)==5&&tickets) 59 { 60 61 for(int i=0;i<tickets;i++) 62 { 63 scanf("%d",&cnt[i]); 64 } 65 memset(edges,-1,sizeof(edges)); 66 for(int i=0;i<edge;i++) 67 { 68 int x,y,z; 69 scanf("%d%d%d",&x,&y,&z); 70 edges[x-1][y-1]=edges[y-1][x-1]=z; 71 } 72 solve(); 73 } 74 return 0; 75 }