L3-011 直捣黄龙 （暴力动态递归）
| 本题是一部战争大片 —— 你需要从己方大本营出发，一路攻城略地杀到敌方大本营。首先时间就是生命，所以你必须选择合适的路径，以最快的速度占领敌方大本营。当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。 输入格式：输入第一行给出 2 个正整数 N（2 ≤ N ≤ 200，城镇总数）和 K（城镇间道路条数），以及己方大本营和敌方大本营的代号。随后 N-1 行，每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量，其间以空格分隔。再后面有 K 行，每行按格式 输出格式：按照题目要求找到最合适的进攻路径（题目保证速度最快、解放最多、杀伤最强的路径是唯一的），并在第一行按照格式 |
输入样例：
10 12 PAT DBY DBY 100 PTA 20 PDS 90 PMS 40 TAP 50 ATP 200 LNN 80 LAO 30 LON 70 PAT PTA 10 PAT PMS 10 PAT ATP 20 PAT LNN 10 LNN LAO 10 LAO LON 10 LON DBY 10 PMS TAP 10 TAP DBY 10 DBY PDS 10 PDS PTA 10 DBY ATP 10输出样例：
PAT->PTA->PDS->DBY 3 30 210
考察 : 多重条件的最短路 |
注意 : 求的不是'最短路拥有的路径数',而是'最短路有几条' |
思路 ：暴力美学road[a] -> a 通往的路径
length[{a,b}] -> a与b之间的路长
nums[a] -> 城市 a 中敌军的数量
start , end , 数据读入
op 记录动规 , result 结果存储
minFlag 最短路的长度 , kpl 当前最大杀敌数 , minNum 最短路径的条数
now 当前所在位置 ,minRoad 当前路长 , kill 当前 KDA
|
C/C++
#include
using namespace std;
unordered_map> road;
map,int> length;
unordered_map nums;
string st,ed,id1,id2;
vector op,result;
int minFlag=999999,kpl=0,minNum;
void findRoad(string now,int minRoad,int kill);
int main()
{int N,K,num,len;cin >> N >> K >> st >> ed;for(int z=1;z> id1 >> num;nums[id1] = num;}while (K--){cin >> id1 >> id2 >> len;length[{id1,id2}] = length[{id2,id1}] = len;road[id1].push_back(id2);road[id2].push_back(id1);}findRoad(st,0,0);for(string x:result) cout << x << "->";cout << ed << endl;cout << minNum << " " << minFlag << " " << kpl;return 0;
}
unordered_map apr; // apr[a] 判断 a 经过没
void findRoad(string now,int minRoad,int kill){if(now==ed){if(minRoadresult.size()||(op.size()==result.size() && kill>kpl)){kpl = kill;result.assign(op.begin(),op.end());}}return;}if(apr[now]) return;apr[now] = true;op.push_back(now);for(string x:road[now]) findRoad(x,minRoad+length[{now,x}],kill+nums[x]);op.pop_back();apr[now] = false;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！