直捣黄龙 【学习进度条6】

L3：直捣黄龙

【题目】

【代码解释】

【可粘贴代码】

有略微改动

#include
using namespace std;
const int N=210;int scnt[N];//到每个城镇的最短路数量
int node[N];//到每个城镇最短路的结点个数 
int e[N][N];//城镇道路
int csnum[N];//城镇敌军数量
int enm[N];//到每个城镇最短路经过的最多敌人 
map<string,int> mp;//城镇名字对应编号 
string city[N];//城镇名字 
string s,t;//己方和敌方
int ss,tt;
int n,k; void dijskra(int cost[],int pre[]){
//优先级：最短路-->最多结点-->最多敌军数 int flag[n+1];flag[ss]=1;for(int i=1;i<n;i++){cost[i]=e[ss][i];flag[i]=0;pre[i]=ss;}//初始化for(int j=1;j<n;j++){//循环n-1次int min=INT_MAX; int minj=ss;for(int i=1;i<n;i++){if(flag[i]==0&&min>cost[i]&&cost[i]!=INT_MAX){min=cost[i];minj=i;}}//找最小flag[minj]=1;for(int i=1;i<n;i++){if(flag[i]==0){if(cost[i] > cost[minj]+e[minj][i]&&e[minj][i]!=INT_MAX){pre[i]=minj;cost[i]=cost[minj]+e[minj][i];scnt[i]=scnt[minj];//最短路替换 node[i]=node[minj]+1;enm[i]=enm[minj]+csnum[i];}else if(cost[i]==cost[minj]+e[minj][i]&&e[minj][i]!=INT_MAX){scnt[i]+=scnt[minj];//最短路增加  if(node[i]<node[minj]+1){//经过minj路段 结点最多pre[i]=minj;node[i]=node[minj]+1; enm[i]=enm[minj]+csnum[i];}else if(node[i]==node[minj]+1){//最多结点数相同，找敌人最多数if(enm[i]<enm[minj]+csnum[i]){pre[i]=minj;enm[i]=enm[minj]+csnum[i];} }}}} //更新  }
}int main(){scanf("%d%d",&n,&k);for(int i=0;i<n;i++){for(int j=0;j<n;j++){e[i][j]=INT_MAX; }} cin>>s>>t;city[0]=s;mp[s]=0;csnum[0]=0;for(int i=1;i<n;i++){cin>>city[i];int num;scanf("%d",&num);mp[city[i]]=i;csnum[i]=num;enm[i]=num;}getchar();for(int i=0;i<k;i++){string u,v;cin>>u>>v;int len;scanf("%d",&len);int a=mp[u];int b=mp[v];e[a][b]=len;e[b][a]=len;//保存路径} int ss=mp[s];//起点 int tt=mp[t];//终点for(int i=1;i<n;i++){if(e[ss][i]!=INT_MAX){scnt[i]=1;node[i]=2;}else{scnt[i]=0;node[i]=1;}} int cost[n+1];int pre[n+1];dijskra(cost,pre);/*for(int i=1;istack<string> st;int i=tt;for(;i!=ss;i=pre[i]){st.push(city[i]);}cout<<s<<"->";while(st.size()>1){string p=st.top();st.pop();cout<<p<<"->";}string p=st.top();st.pop();cout<<p<<endl;cout<<scnt[tt]<<" "<<cost[tt]<<" "<<enm[tt];return 0;
}

代码中起的名字不太恰当可能会造成代码可读性不好，下面两篇感觉还不错，推荐给大家：

1. 相同dijkstra变形的思路的：
   https://www.cnblogs.com/hulian425/p/14049914.html
2. 不同思路——深度优先搜索的：
   https://blog.csdn.net/tobealistenner/article/details/88685014

这个题和城市间紧急救援有些类似，可以参考着来看。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！