首页 > 代码库 > POJ 2686 Traveling by Stagecoach(状压DP)
POJ 2686 Traveling by Stagecoach(状压DP)
【题目链接】 http://poj.org/problem?id=2686
【题目大意】
给出一张无向图,你有n张马车票每张车票可以租用ti匹马,
用一张马车票从一个城市到另一个城市所用的时间为这两个城市间的道路距离除以马的数量
一张马车票只能用一次,问从a到b的最短时间
【题解】
dp[S][u]表示剩余的车票集合为S,到达u所用的最短时间,
之后我们枚举剩余的车票集合,枚举边和用的车票,进行状态转移。
【代码】
#include <cstdio>#include <climits>#include <algorithm>#include <cstring>using namespace std;const int N=10,M=35;const double INF=1000000000;int x,y,c,n,m,a,b,p,t[N],d[M][M];double dp[1<<N][M];int main(){ while(~scanf("%d%d%d%d%d",&n,&m,&p,&a,&b)){ if(n+m+p+a+b==0)break; memset(d,-1,sizeof(d)); for(int i=0;i<n;i++)scanf("%d",&t[i]); for(int i=1;i<=p;i++){ scanf("%d%d%d",&x,&y,&c); d[x-1][y-1]=c; d[y-1][x-1]=c; }for(int S=0;S<1<<n;S++)fill(dp[S],dp[S]+m,INF); dp[(1<<n)-1][a-1]=0; double res=INF; for(int S=(1<<n)-1;S>=0;S--){ res=min(res,dp[S][b-1]); for(int v=0;v<m;v++){ for(int i=0;i<n;i++)if((S>>i)&1){ for(int u=0;u<m;u++){ if(d[v][u]>=0){ dp[S&~(1<<i)][u]=min(dp[S&~(1<<i)][u],dp[S][v]+(double)d[v][u]/t[i]); } } } } }if(res==INF)puts("Impossible\n"); else printf("%.3f\n",res); }return 0; }
POJ 2686 Traveling by Stagecoach(状压DP)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。