PAT甲级-1087 All Roads Lead to Rome (30 分)-白红宇的个人博客

PAT甲级-1087 All Roads Lead to Rome (30 分)

发布日期：2022-02-10 08:10:59 浏览次数：24 分类：技术文章

本文共 1794 字，大约阅读时间需要 5 分钟。

题目：

分析：根据题意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<
                      
                       <<" "<
                       
                        <<" "<
                        
                         <<" "<
                         
                          "<

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

上一篇：PAT甲级-1086 Tree Traversals Again (25 分)

下一篇：PAT甲级-1093 Count PAT‘s (25 分)

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题目：

分析：根据题意DFS即可，只不过城市名是字符串，用map。

发表评论

最新留言

关于作者

推荐文章