Traveling by Stagecoach /// 状压DP oj22914

题目大意：

输入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 Input

3 4 3 1 4
3 1 2
1 2 10
2 3 30
3 4 20
2 4 4 2 1
3 1
2 3 3
1 3 3
4 1 2
4 2 5
2 4 3 4 1
5 5
1 2 10
2 3 10
3 4 10
1 2 0 1 2
1
8 5 10 1 5
2 7 1 8 4 5 6 3
1 2 5
2 3 4
3 4 7
4 5 3
1 3 25
2 4 23
3 5 22
1 4 45
2 5 51
1 5 99
0 0 0 0 0

Sample Output

30.000
3.667
Impossible
Impossible
2.856

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f

#define N 8

using namespace std;

int n,m,p,a,b;

int t[N],G[][];

double dp[<<N][];

void solve()

{

    int st=(<<n)-; /// 注意 1<<n 需要打括号 -比<<优先级高

    for(int i=0;i<=st;i++) /// double型 不能用memset初始化

        fill(dp[i],dp[i]+m,INF);

    dp[st][a-]=; // 初始状态 车票都在且位于a点 1为还没用 0为已用

    double ans=INF;

    for(int p=st;p>=;p--){ // 枚举所有车票状态

        ans=min(ans,dp[p][b-]); // 更新到达b点的最少时间

        for(int i=;i<m;i++) { // 枚举所在点

            if(dp[p][i]==INF) continue;

            /// 若车票状态为p且位于i点的dp值为INF

            /// 说明当前还未能更新出该情况 则忽略

            for(int k=;k<n;k++) // 枚举接下来要使用的车票

                if((<<k)&p) { /// 若车票状态p中 还没用过k车票

                    for(int j=;j<m;j++) { // 枚举使用k车票要去的点

                        if(G[i+][j+]==INF) continue; // 没有路则忽略

                        double tmp=(double)G[i+][j+]/t[k]; /// 该路使用k车票需要的时间

                        dp[p&~(<<k)][j]=min(dp[p&~(<<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=;i<n;i++) scanf("%d",&t[i]);

        if(n+m+p+a+b==) break;

        if(p== || n==) { // 没有路或没有车票

            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 ;

}

巴特西

Traveling by Stagecoach /// 状压DP oj22914

最新文章

热门文章