PAT 甲级 1003 Emergency (25 分)-蒲公英云

PAT 甲级 1003 Emergency (25 分)

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

在这里插入图片描述
纪念一下我接触到的第一道算法题
一开始完全没有头绪，用普通的暴力方法总是难以遍历每种可能
看了很多大佬的代码后发现了可以用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;
}