题目大意：
输入n，m，p，a，b
n是车票数（1<=n<=8），m是城市数（2<=m<=30）
p是路径数（可能为0），a是起点，b是终点
接下来一行有n个数 为每张车票的马匹数
接下来p行有u，v，w为城市u到城市v路径长度为w
时间计算为 路径长度/车票马匹数
求a到b的最短用时，不可能则输出 Impossible
最后一行以5个0结束
Sample Input3 4 3 1 43 1 21 2 102 3 303 4 202 4 4 2 13 12 3 31 3 34 1 24 2 52 4 3 4 15 51 2 102 3 103 4 101 2 0 1 218 5 10 1 52 7 1 8 4 5 6 31 2 52 3 43 4 74 5 31 3 252 4 233 5 221 4 452 5 511 5 990 0 0 0 0
Sample Output30.0003.667ImpossibleImpossible2.856
#include <bits/stdc++.h> #define INF 0x3f3f3f3f #define N 8 using namespace std; int n,m,p,a,b; int t[N],G[35][35]; double dp[1<<N][35]; void solve() { int st=(1<<n)-1; /// 注意 1<<n 需要打括号 -比<<优先级高 for(int i=0;i<=st;i++) /// double型 不能用memset初始化 fill(dp[i],dp[i]+m,INF); dp[st][a-1]=0; // 初始状态 车票都在且位于a点 1为还没用 0为已用 double ans=INF; for(int p=st;p>=0;p--){ // 枚举所有车票状态 ans=min(ans,dp[p][b-1]); // 更新到达b点的最少时间 for(int i=0;i<m;i++) { // 枚举所在点 if(dp[p][i]==INF) continue; /// 若车票状态为p且位于i点的dp值为INF /// 说明当前还未能更新出该情况 则忽略 for(int k=0;k<n;k++) // 枚举接下来要使用的车票 if((1<<k)&p) { /// 若车票状态p中 还没用过k车票 for(int j=0;j<m;j++) { // 枚举使用k车票要去的点 if(G[i+1][j+1]==INF) continue; // 没有路则忽略 double tmp=(double)G[i+1][j+1]/t[k]; /// 该路使用k车票需要的时间 dp[p&~(1<<k)][j]=min(dp[p&~(1<<k)][j],dp[p][i]+tmp); /// 通过p状态位于j点花费tmp dp[p][i]+tmp /// 延伸到k车票已用位于i点的状态 dp[p&~(1<<k)][j] } } } } // for(int s=0;s<=(1<<n)-1;s++) { // for(int i=1;i<=m;i++) // if(dp[s][i]==INF) printf("-1 "); // else printf("%.3f ",dp[s][i]); // printf("\n"); // } if(ans==INF) printf("Impossible\n"); else printf("%.3f\n",ans); } int main() { while(~scanf("%d%d%d%d%d",&n,&m,&p,&a,&b)) { for(int i=0;i<n;i++) scanf("%d",&t[i]); if(n+m+p+a+b==0) break; if(p==0 || n==0) { // 没有路或没有车票 printf("Impossible\n"); continue; } if(a==b) { // 起点终点为同一点 printf("0\n"); continue; } memset(G,INF,sizeof(G)); while(p--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); G[u][v]=G[v][u]=min(G[u][v],w); } solve(); } return 0; } View Code
转载于:https://www.cnblogs.com/zquzjx/p/9148724.html
