hdu4848 求到达每个点总时间最短（sum[d[i]]）。

开始的时候是暴力dfs+剪枝，怎么也不行。后来参考他人思想：

先求出每个点之间的最短路（这样预处理之后的搜索就可以判重返回了），截肢还是关键：1最优性剪枝（尽量最优：目前的状态+预计还有的最小时间>min就return !），2：可行性截肢：如果当前状态+预计状态已经不可行，return。（注意考虑是 continue，还是 return !）.以及放的位置！在出口放的效果一般好一些（不在下次循环内部）（理由：若该状态是后面的状态进入的，前面的会dfs到很深，所以，放在最前面，一起判断下，不行就return 一般比较合理。）

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n;int da[35];int d[35];

int a[35][35];

int maxd=0;

const int inf=0x3f3f3f3f;

int minn=inf;

int bit[31];

void dfs(int x,int lev,int sum,int allstate)

{

    if(sum+d[x]*(n-lev)>=minn||d[x]>maxd){return;}

    if(allstate==(bit[n]-1))

     {

        minn=sum;

        return;

     }

     for(int i=2;i<=n;i++)

    {

       if((allstate&bit[i-1])==0&&d[x]+a[x][i]>da[i])

               return;

    }

    for(int i=2;i<=n;i++)

    {

       if((allstate&bit[i-1])==0)

       {

           int f=d[i];

           d[i]=d[x]+a[x][i];

          dfs(i,lev+1,sum+d[i],allstate|bit[i-1]);

           d[i]=f;

       }

    }

    return ;

}

void init()

{

    int td=0;

    da[1]=0x3f3f3f3f-1;

    for(int i=1;i<=n;i++)

        d[i]=inf;

    d[1]=0;

    maxd=0;

    minn=inf;

    for(int i=1;i<=n;i++)                       //之前又犯错！先枚举过度点！

      for(int j=1;j<=n;j++)

        for(int k=1;k<=n;k++)

           if(a[j][i]+a[i][k]<a[j][k])

               a[j][k]=a[j][i]+a[i][k];

}

int main()

{

    for(int i=0;i<31;i++)

        bit[i]=1<<i;

    while(scanf("%d",&n)!=EOF)

    {

        for(int i=1;i<=n;i++)

         for(int j=1;j<=n;j++)

            scanf("%d",&a[i][j]);

         init();

        for(int i=2;i<=n;i++)

           {

                scanf("%d",&da[i]);

              if(da[i]>maxd)maxd=da[i];

           }

          dfs(1,1,0,1);

          if(minn!=inf)

            printf("%d\n",minn);

          else

            printf("-1\n");

    }

    return 0;

}

巴特西

hdu4848 求到达每个点总时间最短（sum[d[i]]）。

最新文章

热门文章