PTA 直捣黄龙

• PTA直捣黄龙的题解
• • 基本思路
  • 整体算法如下：

PTA直捣黄龙的题解

基本思路

一些记录数据的数据结构：

map<string,int> mmp1;
map<int,string> mmp2;   //映射据点名字和编号int gra[205][205];  //存储图
int num[205];       //每个据点的敌人的数量
int tot[205];       //到达一据点，所能歼灭敌军的数量
int pth[205];       //到达一据点，最短路径的数量
int rot[205];       //记录路径
int tia[205];       //到达一据点，所解放的据点的总数
int dis[205];       //最短路
int vis[205];       //标记数组

在进行Dijkstra算法时，作一些适当的变形，即可解决问题：

if(dis[j] > dis[pres]+gra[pres][j]){     //找到更短的路径dis[j] = dis[pres]+gra[pres][j];     //更新最短路大小tot[j] = tot[pres]+num[j];           //记录歼灭敌军总数rot[j] = pres;                       //记录路径tia[j] = tia[pres]+1;                //经历据点数+1pth[j] = pth[pres];                  //传递最短路径数
}
else if(dis[j] == dis[pres]+gra[pres][j]){ //找到另一条最短路径pth[j]+= pth[pres];                    //更新最短路径数if(tia[j] < tia[pres]+1) {             //最短路不唯一，如果能解放更多的据点tia[j] = tia[pres]+1;              //更新经历的据点数rot[j]=pres;                       //记录路径tot[j] = tot[pres]+num[j];         //记录歼灭敌军总数}else if(tia[j] == tia[pres]+1){         //最短路和经历据点数都相同的路径不唯一if(tot[j] < tot[pres]+num[j]){      //如果能杀伤更多敌军rot[j]=pres;                    //记录路径tot[j] = tot[pres]+num[j];      //更新歼灭敌军数}}
}

整体算法如下：

#include
using namespace std;
#define INF 0x3f3f3f3f
int n,m;
string sta,ed;          //起点、终点
map<string,int> mmp1;
map<int,string> mmp2;   //映射据点名字和编号int gra[205][205];  //存储图
int num[205];       //每个据点的敌人的数量
int tot[205];       //到达一据点，所能歼灭敌军的数量
int pth[205];       //到达一据点，最短路径的数量
int rot[205];       //记录路径
int tia[205];       //到达一据点，所解放的据点的总数
int dis[205];       //最短路
int vis[205];       //标记数组
//变形的Dijkstra算法
void dij() {for(int i=0;i<n;i++)dis[i]=gra[mmp1[sta]][i];for(int i=0;i<n;i++){int mins=INF;int pres=mmp1[sta];for(int j=0;j<n;j++){if(!vis[j] && dis[j]<mins){mins=dis[j];pres=j;}}if(mins>=INF) break;vis[pres]=1;for(int j=0;j<n;j++) {if(vis[j])continue;if(dis[j] > dis[pres]+gra[pres][j]){     //找到更短的路径dis[j] = dis[pres]+gra[pres][j];     //更新最短路大小tot[j] = tot[pres]+num[j];           //记录歼灭敌军总数rot[j] = pres;                       //记录路径tia[j] = tia[pres]+1;                //经历据点数+1pth[j] = pth[pres];                  //传递最短路径数}else if(dis[j] == dis[pres]+gra[pres][j]){ //找到另一条最短路径pth[j]+= pth[pres];                    //更新最短路径数if(tia[j] < tia[pres]+1) {             //最短路不唯一，如果能解放更多的据点tia[j] = tia[pres]+1;              //更新经历的据点数rot[j]=pres;                       //记录路径tot[j] = tot[pres]+num[j];         //记录歼灭敌军总数}else if(tia[j] == tia[pres]+1){         //最短路和经历据点数都相同的路径不唯一if(tot[j] < tot[pres]+num[j]){      //如果能杀伤更多敌军rot[j]=pres;                    //记录路径tot[j] = tot[pres]+num[j];      //更新歼灭敌军数}}}}}
}int main() {mmp1.clear();mmp2.clear();scanf("%d %d ",&n,&m);cin>>sta;cin>>ed;for(int i=0;i<205;i++){num[i]=0;rot[i]=-1;tot[i]=0;pth[i]=0;tia[i]=0;dis[i]=0;vis[i]=0;for(int j=0;j<205;j++){gra[i][j] = (i==j) ? 0 : INF;}}string uss,vss;mmp2[0]=sta;mmp1[sta]=0;for(int i=1;i<n;i++) {     cin>>vss;scanf(" %d ",&num[i]);mmp1[vss]=i;mmp2[i]=vss;}for(int i=0;i<m;i++){int cst;cin>>uss;cin>>vss;scanf("%d",&cst);gra[mmp1[uss]][mmp1[vss]]=gra[mmp1[vss]][mmp1[uss]]=cst;}pth[0]=1;dij();vector<int> ptan;ptan.clear();int sstp=mmp1[ed];while(sstp!=-1){ptan.push_back(sstp);sstp=rot[sstp];}int lp=ptan.size();for(int i=0;i<lp;i++){cout<<mmp2[ptan[lp-1-i]];printf("%s",(i==lp-1)?"\n":"->");}cout<<pth[mmp1[ed]]<<" "<<dis[mmp1[ed]]<<" "<<tot[mmp1[ed]]<<endl;system("pause");return 0;
}

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