Tancode

用户名：dotcpp0736875

访问量：61

签　名：

等　　级
排　　名	57956
经　　验	237
参赛次数	0
文章发表	1
年　　龄	0
在职情况	学生
学　　校	青岛大学
专　　业

　　自我简介：

TA的其他文章

dfs自用--自用
浏览：51

你可能喜欢

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

dfs自用--自用

　　作者: Tancode　　　　发表时间：2024-05-02 13:39:52 浏览：51　|　评论：0　

原题链接：蓝桥杯2022年第十三届决赛真题-出差

#include <bits/stdc++.h>
    using namespace std;
    const int MAXN = 1005;
    int city[MAXN];
    int a[MAXN][MAXN];
    int m,n,u,v,c;
    long long ans = 10000;
    int f[MAXN] = {0};  //f防止重复经过这个城市
    void dfs(int x,long long  time){  //a是当前的城市，time是在此之前已经花费的时间
        f[x] = 1;  //代表该城市已经来过
        if(time > ans) return; 
        if(x == n){   // 如果到最后一个城市了，那么就记录答案
            ans = min(time,ans);
           f[x] = 0;
           return;
        }
        if(x!=n){
            for(int i = 1; i <=n;i++){
                if(f[i] == 0 && a[x][i]!=0){
                    //如果这个城市有航线且没来过这个城市
                    dfs(i,time+city[x]+a[x][i]);
                    //我好像把 f[x]置0放错位置了，放循环外面的话，会影响下次遍历，因此要放里面
                    f[i] = 0; //就是因为多个这个，这道题就过了
                }
            }
        }
        //这条航班经历过该城市，另一种路线要经历该城市的话，需要在跳出该栈时先将f[x]置0
        f[x] = 0;
    
    
    }
    int main(){
        cin>>n>>m;
        for (int i=1; i<=n; i++){
            cin>>city[i];
        }
        city[1] = city[n] = 0;   //第一个城市和最后一个城市不需要考虑隔离
        for(int i = 0;i<m; i++){
            cin>>u>>v>>c;
            a[u][v] = a[v][u] = c;
        }
        dfs(1,0);
        cout << ans;
        return 0;
    }

0.0分

0 人评分

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

　　评论区

精彩推荐

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

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

本人酷爱递归实现很多问题，这里也是

IP判断（C语言代码）

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

字符逆序（C语言代码）

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

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

Manchester- A+B for Input-Output Practice (I)

WU-震宇大神的杀毒软件（C++代码）

Tancode

TA的其他文章

你可能喜欢

1065

化学品问题（C语言代码）

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

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

【亲和数】（C语言代码）

dfs自用--自用

评论区

精彩推荐

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

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

本人酷爱递归实现很多问题，这里也是

IP判断（C语言代码）

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

字符逆序（C语言代码）

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

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

Manchester- A+B for Input-Output Practice (I)

WU-震宇大神的杀毒软件（C++代码）

Tancode

TA的其他文章

你可能喜欢

1065

化学品问题 （C语言代码）

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

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

【亲和数】 （C语言代码）

dfs自用--自用

评论区

精彩推荐

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

C语言训练-阶乘和数* （C语言代码）-------- 呆板写法

本人酷爱递归实现很多问题，这里也是

IP判断 （C语言代码）

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

字符逆序 （C语言代码）

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

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

Manchester- A+B for Input-Output Practice (I)

WU-震宇大神的杀毒软件 （C++代码）

化学品问题（C语言代码）

【亲和数】（C语言代码）

　　评论区

IP判断（C语言代码）

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

字符逆序（C语言代码）

WU-震宇大神的杀毒软件（C++代码）