ajsdashjbd

用户名：lqbgsdy

访问量：13476

签　名：

等　　级
排　　名	992
经　　验	3288
参赛次数	12
文章发表	6
年　　龄	0
在职情况	学生
学　　校	ccgc
专　　业

　　自我简介：

TA的其他文章

最多约数问题（C++代码）
浏览：4418

1017题完数的判断-题解(C++代码)（筛法求解）
浏览：2278

开心的金明-题解(C++代码) 背包问题
浏览：2555

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

蓝桥杯算法提高VIP-文化之旅-题解(C++代码)

　　作者: ajsdashjbd　　　　发表时间：2019-07-11 15:48:43 浏览：708　|　评论：0　

原题链接：蓝桥杯算法提高VIP-文化之旅

表示这道题不需要什么最短路算法(感觉这样写是错的) 也并不需要倒着搜索 其实只需要多一个与终点的判断就可以了

```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
using namespace std;
const int Inf=100000010;
int n,m,k,s,t;
int k1=0,sum=0,ans=Inf;
int con[110],head[20010],fig[110][110];//con[i]=j表示第i个国家冲突第j种文化 fig[i][j]表示i j文化关系 
bool road[110],exp[110],flag=false;//road表示已访问的国家 exp表示已访问的文化 
struct node{
    int to,next,w;
}e[20010];
void add(int u,int v,int w)
{
    k1++;
    e[k1].next=head[u];
    e[k1].to=v;
    e[k1].w=w;
    head[u]=k1;
}
bool judge(int x)
{
  if(road[x] || exp[con[x]]) return false;
   for(int i=1;i<=k;i++)
    if(exp[i]&&fig[con[x]][i]==1||fig[con[t]][con[x]]==1||fig[con[t]][i]) return false;
    //后两个判断表明如果终点的文化冲突已经学过的文化和访问次国家的文化 则return false 
     return true;
}
void dfs(int x,int sum)
{
    bool ff=false;
  if(x==t){
      flag=true;
      ans=min(ans,sum);
      return ;
  }
  if(sum>=ans) return;//剪枝 
  for(int i=head[x];i;i=e[i].next)
  {
      int p=e[i].to;
      if(judge(p))
      {
        ff=true;//判断是否可以往下走 
        road[p]=true,exp[con[p]]=true;
        dfs(p,sum+e[i].w);
        road[p]=false,exp[con[p]]=false;
    }
  }
  if(ff==false){
      printf("-1");//如果没有往下走 这直接打印-1并退出 
      exit(0);
  }
}
int main()
{
    memset(road,false,sizeof(road));
    memset(exp,false,sizeof(exp));
    scanf("%d%d%d%d%d",&n,&k,&m,&s,&t);
    for(int i=1;i<=n;i++) scanf("%d",&con[i]);
    for(int i=1;i<=k;i++)
     for(int j=1;j<=k;j++) 
      scanf("%d",&fig[i][j]);
    int x,y,z;
    for(int i=1;i<=m;i++)
    {
      scanf("%d%d%d",&x,&y,&z);
      sum+=z;
      add(x,y,z);
      add(y,x,z);
    }  
    exp[con[s]]=true;
    dfs(s,0);
    if(ans>sum||flag==false) printf("-1");
    else printf("%d",ans);
    return 0;
} 
```

0.0分

10 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

ajsdashjbd

TA的其他文章

你可能喜欢

C二级辅导-温度转换（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

上车人数（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

蓝桥杯算法提高VIP-文化之旅-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

简单编码（C++代码）

弟弟的作业（C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

【蟠桃记】（C语言代码）

1035 题解

程序员的表白（C语言代码）

链表数据求和操作（C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

ajsdashjbd

TA的其他文章

你可能喜欢

C二级辅导-温度转换 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

上车人数 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

蓝桥杯算法提高VIP-文化之旅-题解(C++代码)

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题12.6 （C语言代码）

简单编码 （C++代码）

弟弟的作业 （C++代码）

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C++代码）

【蟠桃记】 （C语言代码）

1035 题解

程序员的表白 （C语言代码）

链表数据求和操作 （C语言代码）

C语言程序设计教程（第三版）课后习题12.1 （C语言代码）

C二级辅导-温度转换（C语言代码）

上车人数（C语言代码）

　　评论区

简单编码（C++代码）

弟弟的作业（C++代码）

【蟠桃记】（C语言代码）

程序员的表白（C语言代码）

链表数据求和操作（C语言代码）