首页 > 代码库 > poj3311(Hie with the Pie)状压dp
poj3311(Hie with the Pie)状压dp
题目链接:http://poj.org/problem?id=3311
解法:标准的状压dp类型,先floyd获得两两之间最短距离。然后dp[i][j]表示剩下集合i没走,已经走到j的最短距离;
代码:
/****************************************************** * @author:xiefubao *******************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <iostream> #include <cstring> #include <cstdlib> #include <cstdio> #include <queue> #include <vector> #include <algorithm> #include <cmath> #include <map> #include <set> #include <stack> #include <string.h> //freopen ("in.txt" , "r" , stdin); using namespace std; #define eps 1e-8 #define zero(_) (abs(_)<=eps) const double pi=acos(-1.0); typedef long long LL; const int Max=15; const int INF=1e9+7; int dist[Max][Max]; int dp[(1<<13)+3][13]; int n; int getans(int st,int la) { if(dp[st][la]!=-1) return dp[st][la]; int ans=INF; for(int i=0; i<=n; i++) { if((st&(1<<i))&&la!=i) ans=min(ans,getans(st-(1<<la),i)+dist[la][i]); } // cout<<ans<<endl; return dp[st][la]=ans; } int main() { while(scanf("%d",&n)==1&&n) { for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) scanf("%d",dist[i]+j); for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) for(int k=0; k<=n; k++) dist[j][k]=min(dist[j][i]+dist[i][k],dist[j][k]); int ans=INF; memset(dp,-1,sizeof dp); dp[1][0]=0; for(int i=1; i<=n; i++) ans=min(ans,getans((1<<(n+1))-1,i)+dist[0][i]); printf("%d\n",ans); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。