pku_2686_Traveling by Stagecoach

 

Traveling by Stagecoach

 

 

【题目概述】告诉一张地图,地图上有N(2<=2<= 30)个城市,由一个城市到另外一个城市的唯一交通工具是马车,不同型号的马车花费的时间(这里的时间计算用两地的距离除以该马车骂的数量,马越多越快)不一样。现在给你N(1<=N<=8)两马晨,每辆马车告诉马的数量,求有一个城市到另外一个城市的最短时间。

【题目分析】参考了hobby的代码,和froeverLin提示,在这里予以说明。

像是一个最短路问题,但是增加了限制条件,解法DP毋庸置疑,给定马车的数量<= 8 状态压缩DP.

要求的仅仅是最短的时间,没有求分配方案,这无疑使问题简单话了。

影响节点(城市)之间的花费的唯一变化因素是马的数量(距离是固定的)。

  表示当前状态为s,走到城市j的最小时间。

状态转移方程,为 对于任何一个与j相连的节点k

 

其中, r为和k相连的城市, r为不在s中的某个马车的加入后的状态, t[w]为该马车的马匹数。

初始化问题。

由于求的是最小值,我们初始化dp为某个最大值。

for(p = 1; p < (1<<n); p++)

            for(i = 0; i < m; i++) dp[p][i] = inf;

 

由于每次都是从a开始的,所以初始化的时候要初始化和a与关系的边的转移。

        for (i = 0; i < m; i++) if(map[a][i] != -1)

            for(k = 0; k < n; k++) dp[1<<k][i] = map[a][i]/t[k];

【题目代码】

//Name: pku_2686_Traveling by Stagecoach

// dp[i][j]表示当前使用的票的状态为i到达了j城市的最少用时

// 若第k个城市与j相连通,且,枚举枚举票数最少的

#include <iostream>

using namespace std;

#define inf 1<<30

int map[30][30];

int n, m, p, a, b, d, r, q;

double dp[1<<8][30], t[30], tmp, ans;

int main() {

   // freopen("in.in", "r", stdin);

    int i, j, k, x, y;

    while(scanf("%d%d%d%d%d",&n,&m,&p,&a,&b) != EOF) {

        if (!(n||m||p||a||b)) break;

        a--; b--;

        for(i = 0; i < n; i++) scanf("%lf", t+i);

        memset(map, -1,sizeof(map));

        for (i = 1; i <= p; i++) {

            scanf("%d %d %d", &x, &y, &d); x--;y--;

            map[x][y] = map[y][x] = d;

        }

        for(p = 1; p < (1<<n); p++)

            for(i = 0; i < m; i++) dp[p][i] = inf;

        for (i = 0; i < m; i++) if(map[a][i] != -1)

            for(k = 0; k < n; k++)

                 dp[1<<k][i] = map[a][i]/t[k];

        for (p = 1; p < (1<<n); p++) {

            for (j = 0; j < m; j++) if(dp[p][j] != inf) {

                for (k = 0; k < m; k++) if(k!=j && map[j][k]!=-1) {

                    for (r = 0; r < n; r++) if(!(p&(1<<r))) {

                        q = p + (1<<r);

                        tmp = dp[p][j] + map[j][k] /t[r];

                        if (dp[q][k] > tmp) dp[q][k] = tmp;

                    }

                }

            }

       }

       ans = inf;

       for (p = 1; p < (1<<n); p++)

            if(dp[p][b] < ans) ans = dp[p][b];

       if(ans == inf) printf("Impossible\n");

       else printf("%lf\n", ans);

   }

}           

posted on 2010-08-08 14:01 小志 阅读(199) 评论(0)  编辑 收藏 引用


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿

随笔档案(8)

文章档案(1)

相册

收藏夹

ACM --- Online Judge

小志

最新随笔

积分与排名

最新随笔

最新评论

阅读排行榜

评论排行榜