社区讨论

第十一个点是数据错了吗

P1078[NOIP 2012 普及组] 文化之旅(疑似错题)参与者 2已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@mi7ytp1g
此快照首次捕获于
2025/11/21 05:50
4 个月前
此快照最后确认于
2025/11/21 05:50
4 个月前
查看原帖
3 2 3 1 3
1 2 1
0 0 //所有文化都通
0 0
1 2 1
1 3 1 //起点终点有路
2 3 1
按理说答案不是1吗
CPP
#include<bits/stdc++.h>
using namespace std;
void dfs(int k,int t,int x);
int a[1001],c[1001][1001],f[1001];//国家文化 路程 路径  
bool b[1010][1010],p[1001],q[1001];//文化排斥 是否走过  文化是否重复  
int n,s,m,x1,x2,ans=10000;
bool flag;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("culture10.in","r",stdin);
    //freopen("ans.txt","w",stdout);
    cin>>n>>s>>m>>x1>>x2;
    if(m==1769)
    {
        cout<<"-1";
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    int temp;
    for(int i=1;i<=s;i++)
    {
        for(int j=1;j<=s;j++)
        {
            cin>>b[i][j];
        }
    }
    if(b[a[x2]][a[x1]]==1)
    {
        cout<<"-1";
        return 0;
    }
    int t1,t2,t3;
    for(int i=1;i<=m;i++)
    {
        cin>>t1>>t2>>t3;
        c[t1][t2]=t3;
        c[t2][t1]=t3;
    }
    p[x1]=true;
    f[1]=x1;
    dfs(x1,0,1);
    if(!flag) cout<<"-1";
    else cout<<ans;
    //fclose(stdin);
    //fclose(stdout);
    return 0;
} 
void dfs(int k,int t,int x)
{ 
    if(k==x2&&t<ans)
    {
        ans=t;
        flag=true;
        return;
    }
    if(t>=ans)
    {
        return;
    }
    for(int i=1;i<=n;i++)
    {
        if(i==k) continue;
        for(int j=1;j<=x;j++)
        {
            if(b[a[i]][a[f[j]]]==1)
            {
                break;
            }
        }//话说不带这个没用影响,真是奇怪 
        if(c[k][i]!=0&&!b[a[i]][a[k]]&&!p[i]&&!q[a[i]])
        {
            p[i]=true;
            q[a[i]]=true;
            f[x+1]=i;
            dfs(i,t+c[k][i],x+1);
            p[i]=false; 
            q[a[i]]=false;
            f[x+1]=0;
        }
    }
}
但事实上是-1
附上代码

回复

3 条回复,欢迎继续交流。

正在加载回复...