PAT 甲级 1003 Emergency (25 分)

红太狼 2023-08-17 16:03 63阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]  
纪念一下我接触到的第一道算法题  
一开始完全没有头绪，用普通的暴力方法总是难以遍历每种可能  
看了很多大佬的代码后发现了可以用DFS算法遍历求解，思路如下：  
1.用一个二维数组存储两城市间的距离，同时设置一个visit标记，在该城市的循环下，如果已经访问过某个城市，标记为1，避免重复访问，形成环  
2.在遍历的过程中，记录当前路径的总长度，和总救援人数，如果符合题目要求，更新数据。  
3.特别要注意的一点是对于一个结点，不允许有回路，但是如果从其他结点出发，是可以访问当前结点的，这就需要从一个结点遍历完所有可能后，将visit标记重新赋值为0

#include<iostream>
    using namespace std;
    const int maxn= 505;
    int visit[maxn];//记录是否访问过
    int length[maxn][maxn];//城市间距离
    int men[maxn];//每个城市的救援人数
    int shortest_length=1000000000,shortest_num=1,maxmen=0;
    int n,m,c1,c2;
    void DFS(int cur,int cur_length,int cur_men)
    { 
        if(cur_length>shortest_length)return;
        if(cur==c2)//到达终点
        { 
            if(cur_length<shortest_length)
            { 
                shortest_length = cur_length;
                shortest_num=1;
                maxmen=cur_men;
            }
            else if(cur_length==shortest_length)
            { 
                shortest_num++;
                if(cur_men>maxmen)
                maxmen=cur_men;
            }
            return;
        }
        visit[cur]=1;
        for(int i=0;i<n;i++)//当前结点出发，遍历所有到其他城市的可能
        { 
            if(visit[i]==1||length[cur][i]==0)continue;
            DFS(i,cur_length+length[cur][i],cur_men+men[i]);
        }
        visit[cur]=0;//标记设为0，从其他结点出发可以访问当前结点
    }
    int main()
    { 
        cin>>n>>m>>c1>>c2;
        for(int i=0;i<n;i++)//读入每个城市的救援人数
        { 
            cin>>men[i];
        }
        for(int i=0;i<m;i++)//读入城市间距离
        { 
            int l1,l2,l3;
            cin>>l1>>l2>>l3;
            length[l1][l2]=length[l2][l1]=l3;
        }
        DFS(c1,0,men[c1]);
        cout<<shortest_num<<" "<<maxmen;
        return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI0MDY2Nw_size_16_color_FFFFFF_t_70]: /images/20230810/a556b017a51f42f19cb5fc139bcc0708.png