求助!!

"去第k 个城市的条件是,前k-1 个城市都要被去过"是啥意思??

1 条评论

  • @ 2014-10-31 23:59:38

    求神犇找错啊
    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cstdlib>
    #include<cmath>
    #include<algorithm>
    using namespace std;
    const int maxn=200000000;
    int n,map[102][102],x=0,book[102],finalans=maxn;
    bool judge1(int a[],int n)
    {
    for(int i=1;i<=n;i++)
    if(a[i]==0) return false;
    return true;

    }
    bool judge2(int a[],int b)
    {
    for(int i=1;i<b;i++)
    if(a[i]==0) return false;
    return true;

    }
    int dfs(int a,int b,int c)
    {
    if(judge1(book,n)==true) return 0;
    int ans=maxn,i,j,k;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    for(k=1;k<=n;k++)
    {
    if(i==a&&j==b&&k==c) continue;
    if(i!=a) {if(judge2(book,i)==false) continue;}
    if(j!=b) {if(judge2(book,j)==false) continue;}
    if(k!=c) {if(judge2(book,k)==false) continue;}
    book[i]=1;
    book[j]=1;
    book[k]=1;
    ans=min(ans,dfs(i,j,k)+map[a][i]+map[b][j]+map[c][k]);
    book[i]=0;
    book[j]=0;
    book[k]=0;

    }
    return ans;
    }
    int main()
    {
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    for(int j=i+1;j<=n;j++)
    {
    scanf("%d",&x);
    map[i][j]=x;
    map[j][i]=x;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    for(int k=1;k<=n;k++)
    {
    book[i]=1;
    book[j]=1;
    book[k]=1;
    finalans=min(finalans,dfs(i,j,k));

    book[i]=0;
    book[j]=0;
    book[k]=0;
    }
    printf("%d\n",finalans);
    return 0;

    }

  • 1

信息

ID
1547
难度
1
分类
搜索 | 记忆化搜索 点击显示
标签
(无)
递交数
884
已通过
590
通过率
67%
被复制
5
上传者