poj 2686 Traveling by Stagecoach 状态压缩-白红宇

poj 2686 Traveling by Stagecoach 状态压缩

阅读量：4114 次

发布时间：2019-05-25

本文共 1275 字，大约阅读时间需要 4 分钟。

题意：有m个城市,其中有些城市之间有道路连通，且有一定的距离w，现在你有n张卡，每张卡有个权值t能让经过

通过

道路的费用变为w/t，求从城市a到城市b的最小的花费。

#include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             #include 
             
               #include 
              
                using namespace std; #define MM(a) memset(a,0,sizeof(a)) typedef long long ll; typedef unsigned long long ULL; const int mod = 1000000007; const double eps = 1e-10; const int inf = 0x3f3f3f3f; const int big=50000; int max(int a,int b) {return a>b?a:b;}; double min_(double a,double b) {return a
               
                 G[35]; double dp[1<<10][35]; void solve() { double ans=inf; for(int s=0;s<=(1<
                
                 =0;s--) { ans=min_(ans,dp[s][b]); for(int u=1;u<=m;u++)//枚举起点u for(int j=1;j<=n;j++)//使用第j张票 if(s&(1<<(j-1))) for(int i=0;i
                 
                  =inf-1) printf("Impossible\n"); else printf("%.3f\n",ans); } int main() { while(~scanf("%d %d %d %d %d",&n,&m,&p,&a,&b)) { if(!n&&!m&&!p&&!a&&!b) break; for(int i=1;i<=n;i++) scanf("%d",&t[i]); for(int i=1;i<=m;i++) G[i].clear(); int f,t;double c; for(int i=1;i<=p;i++) { scanf("%d %d %lf",&f,&t,&c); G[f].push_back((e){t,c}); G[t].push_back((e){f,c}); } solve(); } return 0; }