PAT甲级-1087 All Roads Lead to Rome (30 分)
发布日期:2022-02-10 08:10:59 浏览次数:6 分类:技术文章

本文共 1862 字,大约阅读时间需要 6 分钟。

题目:
分析:根据题意DFS即可,只不过城市名是字符串,用map。
#include 
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           #include
            
             #include
             
              using namespace std;#define MAX 999999999typedef long long ll;int n,m,k;map
              
               hap;map
               
                visi;map
                
                 
                  >road;map
                  
                   
                    >city;int min_cost = MAX;int max_hap = -1;int num;vector
                    
                     ans;double avg_hap;int c_cost ;int c_hap ;int c_num;vector
                     
                      c_ans;void dfs(string root){ 
                      
   visi[root] = 1;
if(root == "ROM" ){
   if(c_cost < min_cost){
   min_cost = c_cost;
max_hap = c_hap;
num = c_num;
ans = c_ans;
}
else if(c_cost == min_cost && c_hap > max_hap){
   max_hap = c_hap;
num = c_num;
ans = c_ans;
}
else if(c_cost == min_cost && c_hap == max_hap && c_num < num){
   num = c_num;
ans = c_ans;
}
}
else{
   for(int i = 0; i < city[root].size();i++)
{
   if(!visi[city[root][i]] )
{
   c_cost += road[root][city[root][i]];
c_num++;
c_hap += hap[city[root][i]];
c_ans.push_back(city[root][i]);
dfs(city[root][i]);
c_cost -= road[root][city[root][i]];
c_num--;
c_hap -= hap[city[root][i]];
c_ans.pop_back();
}
}
}
visi[root] = 0;}int cnt;void dfs2(string root){
   visi[root] = 1;
if(root == "ROM" && c_cost == min_cost)
cnt++;
else{
   for(int i = 0; i < city[root].size();i++)
{
   if(!visi[city[root][i]] )
{
   c_cost += road[root][city[root][i]];
c_num++;
c_hap += hap[city[root][i]];
c_ans.push_back(city[root][i]);
dfs2(city[root][i]);
c_cost -= road[root][city[root][i]];
c_num--;
c_hap -= hap[city[root][i]];
c_ans.pop_back();
}
}
}
visi[root] = 0;}int main(){
   string sta;
cin>>n>>m>>sta;
for(int i = 0; i < n - 1; i ++)
{
   string x;int p;
cin>>x>>p;
hap[x] = p;
}
for(int i = 0 ; i < m ; i++)
{
   string a,b;
int x;
cin>>a>>b>>x;
road[a][b] = road[b][a] = x;
city[a].push_back(b);
city[b].push_back(a);
}
dfs(sta);
dfs2(sta);
cout< <<" "< <<" "< <<" "< cout<
for(int i = 0 ; i < ans.size();i++)
cout<<"->"<
return 0;}

转载地址:https://blog.csdn.net/qq_43567222/article/details/113742881 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:PAT甲级-1086 Tree Traversals Again (25 分)
下一篇:PAT甲级-1093 Count PAT‘s (25 分)

发表评论

最新留言

第一次来,支持一个
[***.191.171.37]2022年08月17日 22时43分24秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

最新文章

日期对象data及数学对象math 2020-05-04 02:55:22
日期对象 节点操作 重绘和回流 2020-05-04 02:55:22
日期字符串互换 2020-05-04 02:55:22
日期 搜索功能 2020-05-04 02:55:22
日期 2020-05-04 02:55:21
日期 2020-05-04 02:55:21
日期 2020-05-04 02:55:21
日期 2020-05-04 02:55:21
日期 2020-05-04 02:55:21
日期 2020-05-04 02:55:20
日期 2020-05-04 02:55:20
日期 2020-05-04 02:55:20
日期 2020-05-04 02:55:20
日期 2020-05-04 02:55:20
日期 2020-05-04 02:55:19
日期 2020-05-04 02:55:19
日文abap在线帮助文档 2020-05-04 02:55:19
日报:5月2日Web3业界日间消息汇总 2020-05-04 02:55:19
日报:5月1日Web3业界日间消息汇总 2020-05-04 02:55:19
日报:4月30日Web3业界日间消息汇总 2020-05-04 02:55:19