首页 > 代码库 > poj 3311Hie with the Pie

poj 3311Hie with the Pie

2024-07-12 21:36:17   218人阅读

题意：一个送披萨的，每次送外卖不超过10个地方，给你这些地方之间的时间，求送完外卖回到店里的总时间最小。

解法一：

　　这个n不大即使是NP问题也才1E6多一些所以可以dfs（）；具体的回溯方法结合dance link 就可以；

　　

#include <cstdio>#include <algorithm>#include <cmath>#include <cstdlib>#include <cstring>using namespace std;int Map[11][11];int Stack[11],pos;int left[11];int right[11];int n,ans,tmp,num;//比较怕爆栈 放到内存理好void inint(){    ans=0x7fffffff;    pos=0;    for(int i=0;i<=n;i++)        left[i]=i-1,right[i]=i+1;    for(int k=0;k<n;k++)for(int i=0;i<=n;i++)for(int j=0;j<=n;j++)        Map[i][j]=min(Map[i][j],Map[i][k]+Map[k][j]);}void make(){    tmp=Map[0][Stack[0]];    for(int i=1;i<pos;i++)        tmp+=Map[Stack[i-1]][Stack[i]];    tmp+=Map[Stack[pos-1]][0];    ans=min(ans,tmp);}void dfs(){    //system("pause");    if(num==n){make();return;}    for(int i=right[0];i<=n;i=right[i])    {        num++;        right[ left[i] ]=right[i];        left [ right[i]]=left[i];        Stack[pos++]=i;        dfs();        num--;        right[ left[i] ]=i;        left [ right[i]]=i;        pos--;    }}int main(){    while(~scanf("%d",&n))    {        if(n==0) return 0;        for(int i=0;i<=n;i++)            for(int j=0;j<=n;j++)            scanf("%d",&Map[i][j]);        inint();        dfs();        printf("%d\n",ans);    }    return 0;}

解法2 ：我交完了发现怎么都是 0MS  我的200多点；

　　仔细想了想可以用DP 解决NP 问题 dp[i][j] = min( dp[i][j ] , dp[k][j] + dis[k][j] );(dp[i][j] 中 i  是二进制数  每一位表示这一味走没走过；


联系
我们