ajsdashjbd

用户名：lqbgsdy

访问量：14210

签　名：

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

　　自我简介：

TA的其他文章

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

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

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

你可能喜欢

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

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

　　作者: ajsdashjbd　　　　发表时间：2019-07-11 15:48:43 浏览：764　|　评论：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语言程序设计教程（第三版）课后习题8.1 （C语言代码）

C二级辅导-同因查找（C语言代码）

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

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

点我有惊喜！你懂得！

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

评论区

精彩推荐

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

字符串输入输出函数（Java代码）

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

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

回文数(一) （C语言代码）

字符串问题（C语言代码）

兰顿蚂蚁（C++代码）

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

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

局部变量作函数返回值的问题

ajsdashjbd

TA的其他文章

你可能喜欢

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

C二级辅导-同因查找 （C语言代码）

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

C二级辅导-同因查找 （C++代码）（42的倍数，，所以直接递加42输出）

点我有惊喜！你懂得！

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

评论区

精彩推荐

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

字符串输入输出函数 （Java代码）

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

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

回文数(一) （C语言代码）

字符串问题 （C语言代码）

兰顿蚂蚁 （C++代码）

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

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

局部变量作函数返回值的问题

C二级辅导-同因查找（C语言代码）

C二级辅导-同因查找（C++代码）（42的倍数，，所以直接递加42输出）

　　评论区

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

字符串输入输出函数（Java代码）

字符串问题（C语言代码）

兰顿蚂蚁（C++代码）