pta-L3-011 直捣黄龙 dijkstra

题目

题意：求最短路，同等长度下取经过最多城镇的，同等城镇数下取杀敌最多的。

输出最短路径数，最短距离，杀敌数。

题解：

和L2的紧急救援非常类似。三角更新的时候分类讨论即可。

输出是倒序可以用函数递归输出。

地名因为是三个大写字母所以用26进制表示，然后开数组存一下对应关系就好了。

代码：

#include 
#include
#include
#include
using namespace std;
const int inf=0x3f3f3f3f;
int s2n(string s){return (s[0]-'A')*26*26+(s[1]-'A')*26+s[2]-'A';
}
string n2s(int n){char c[3];c[2]=n%26+'A';n/=26;c[1]=n%26+'A';n/=26;c[0]=n%26+'A';string s;s.append(1,c[0]);s.append(1,c[1]);s.append(1,c[2]);return s;
}
int mp[30000];//26进制数到点序号
int re_mp[30000];
int cnt=0;
int add(string s){if(!mp[s2n(s)]){cnt++;mp[s2n(s)]=cnt;re_mp[cnt]=s2n(s);return cnt;}return mp[s2n(s)];
}
int cost[205][205];
int dis[205];
bool vis[205];
int pre[205];
int enemy[205];
int town_num[205];
int enemy_num[205];
int road_num[205];
void dijk(int st,int n){int i,j;memset(vis,false,sizeof(vis));for(i=1;i<=n;i++)dis[i]=inf;dis[st]=0;road_num[st]=1;for(j=1;j<=n;j++){int k=-1;for(i=1;i<=n;i++){if(!vis[i]&&(k==-1||dis[k]>dis[i])){k=i;}}if(k==-1)break;vis[k]=true;for(i=1;i<=n;i++){if(vis[i])continue;if(dis[k]+cost[k][i]town_num[i]){town_num[i]=town_num[k]+1;enemy_num[i]=enemy_num[k]+enemy[i];pre[i]=k;}else if(town_num[k]+1==town_num[i]){if(enemy_num[k]+enemy[i]>enemy_num[i]){enemy_num[i]=enemy_num[k]+enemy[i];pre[i]=k;}}}}}
}
void print(int en){if(pre[en]==0){cout << n2s(re_mp[en]);return ;}print(pre[en]);cout<<"->"<>n>>m;cin>>s;add(s);st=add(s);cin>>s;add(s);en=add(s);for(i=1;i<=n;i++)for(j=1;j<=n;j++)cost[i][j]=inf;for(i=1;i>s;a=add(s);cin>>b;enemy[a]=b;}for(i=1;i<=m;i++){cin>>s;a=add(s);cin>>s;b=add(s);cin>>c;cost[a][b]=cost[b][a]=c;}dijk(st,n);print(en);cout<< endl;cout <

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