本题是一部战争大片 —— 你需要从己方大本营出发一路攻城略地杀到敌方大本营。首先时间就是生命所以你必须选择合适的路径以最快的速度占领敌方大本营。当这样的路径不唯一时要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一则选择可以有效杀伤最多敌军的路径。输入格式输入第一行给出 2 个正整数 N2 ≤ N ≤ 200城镇总数和 K城镇间道路条数以及己方大本营和敌方大本营的代号。随后 N-1 行每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量其间以空格分隔。再后面有 K 行每行按格式城镇1 城镇2 距离给出两个城镇之间道路的长度。这里设每个城镇包括双方大本营的代号是由 3 个大写英文字母组成的字符串。输出格式按照题目要求找到最合适的进攻路径题目保证速度最快、解放最多、杀伤最强的路径是唯一的并在第一行按照格式己方大本营-城镇1-...-敌方大本营输出。第二行顺序输出最快进攻路径的条数、最短进攻距离、歼敌总数其间以 1 个空格分隔行首尾不得有多余空格。输入样例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思路这是一道三条件Dijkstra最短路径问题。分别是路径最短经过城市最多击杀敌人最多。因为这道题的城市全是单词在这里我使用了两个map容器进行映射将城市单词转化为数字便于后续处理。使用vectorintpre[N]记录在最短路径的前提下每个节点的所有父节点配合dfs函数和嵌套vector容器存储所有可能的最短路径。需要注意的是本题其实在解题思路上和“L2-001 紧急救援”有很多相似的地方“L2-001 紧急救援”这道题我之前也发布过解题的代码。AC代码#include bits/stdc.h using namespace std; const int N 666; int n,k;//城镇数 道路条数 struct node { int v; int w; }; vectornodee[N]; mapstring,intcity;//用于映射城市和编号 mapint,stringc; //反向映射城市编号 mapint,intmp;//记录每个城镇敌军数量 priority_queuepairint,intq;//优先队列处理最短路径 vectorintpre[N]; //记录最短路径下的节点父节点 int d[N],cnt[N];//距离路径条数 vectorintfa; vectorvectorintpath; //存储所有可能的最短路径 vectorintans; void Dijkstra(int s) //dijkstra的板子 { for(int i0;in;i) d[i]0x3f3f3f; //初始化所有到起点的距离为无穷大 d[s]0; cnt[s]1; //起点到自己的路径条数为1 q.push({-d[s],s}); while(q.size()) { auto tq.top(); q.pop(); int ut.second; int dv-t.first; if(dvd[u]) continue; //说明之前已经更新过该节点了 for(auto i:e[u]) { int vi.v,wi.w; if(d[v]d[u]w) { d[v]d[u]w; pre[v].clear();//清空 pre[v].push_back(u);//记录当前最短路径下的父节点 cnt[v]cnt[u]; //到v节点的路径数继承了到u节点的路径数 q.push({-d[v],v}); } else if(d[v]d[u]w) { pre[v].push_back(u); cnt[v]cnt[u];//说明有多种情况那么直接累加两种情况 } } } } void dfs(int u)//深搜存储所有可能的路径方案 { fa.push_back(u); if(u1)//1代表的是起点 { vectorintone_pathfa; reverse(one_path.begin(),one_path.end());//反转 path.push_back(one_path); } else { for(auto v:pre[u]) dfs(v); } fa.pop_back(); } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cinnk; string gg,bb; //我方大营 敌方大营 cinggbb; city[gg]1,city[bb]n;//我方大营映射为1敌方大营映射为n c[1]gg,c[n]bb; //再反向映射1就代表我方大营n代表敌方大营 int idx2; for(int i1;in;i) { string str; int w; cinstr; cinw; if(str!bb) { city[str]idx;//依次把其他城市映射为对应的数字 c[idx]str; mp[idx]w;//记录该城市的敌人数量 idx; } else mp[n]w; } for(int i1;ik;i) { string str1,str2; int w; cinstr1str2; cinw; e[city[str1]].push_back({city[str2],w});//邻接表建图 e[city[str2]].push_back({city[str1],w}); } Dijkstra(1); dfs(n); int res-1; //记录最大节点数 int S-1; //记录最多敌人数 for(auto v:path) { int curv.size(); int x0; for(auto id:v) xmp[id];//先统计该方案下击杀的敌人数量 if(curres)//如果经过的城市数量大 { rescur; //更新 Sx; ansv; } else if(curres) { if(xS) { Sx; ansv; } } }//最后ans存储的就是最优方案 for(int i0;ians.size();i) { if(i!ans.size()-1) { coutc[ans[i]]-; } else coutc[ans[i]]\n; } coutcnt[n] d[n] S; return 0; }评测详情