【一只蒟蒻的刷题历程】 【PTA】 A1087 通往罗马的道路 （dijkstra+优先队列）

【一只蒟蒻的刷题历程】 【PTA】 A1087 通往罗马的道路 （dijkstra+优先队列）

确实，从我们的城市到罗马有许多不同的旅游路线。您应该以最低的成本找到客户的路线，同时获得最大的幸福。

输入规格：

每个输入文件包含一个测试用例。对于每种情况，第一行均包含2个正整数N（2≤N≤200）（城市数）和K（城市对之间的路线总数）；然后是起始城市的名称。接下来的N-1行分别给出一个城市的名称和一个整数，代表一个人可以从该城市（起始城市除外）获得的幸福。然后是K行，每行以City1 City2 Cost格式描述两个城市之间的路线。这里的城市名称是由3个大写英文字母组成的字符串，目的地始终是代表罗马的ROM。

输出规格：

对于每个测试用例，我们都应该找到成本最低的路线。如果这样的路线不是唯一的，那么将建议人们获得最大的幸福。如果这样的路线仍然不是唯一的，那么我们输出的平均幸福感最大-法官保证这样的解决方案存在并且是唯一的。

因此，在输出的第一行中，您必须打印4个数字：建议路线的成本最小，成本，幸福度和平均幸福度（仅取整数部分）的不同路线数。然后在下一行中，您应该以City1-> City2-> …-> ROM格式打印路线。

Sample Input:

6 7 HZH
ROM 100
PKN 40
GDN 55
PRS 95
BLN 80
ROM GDN 1
BLN ROM 1
HZH PKN 1
PRS ROM 2
BLN HZH 2
PKN GDN 1
HZH PRS 1

Sample Output:

3 3 195 97
HZH->PRS->ROM

思路：

应该是目前做过最ex的最短路径，比（城市紧急救援）还ex！！

优先级：路径长度(花费) > 点权之和（幸福值） > 平均点权之和

代码：

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
#include <set>
#include <map>
using namespace std;  
struct node{int v;int w;node(int a,int b){v=a;w=b;}friend bool operator<(node a,node b){return a.w>b.w;}
};
const int maxn=250;
const int inf=1<<27;  //到达不了
vector<node> g[maxn]; //存图
priority_queue<node> p;  //优先队列优化
bool vis[maxn]={false}; //是否走过
int n,k;
map<string,int> m1; //道路名称对应的编号
map<int,string> m2; //编号对应的道路名称
int weight[maxn]={0},dis[maxn],aveweight[maxn],num[maxn],numweight[maxn];
//点权，距离，平均点权，最短路径数，总点权
int pre[maxn],cnt[maxn];
//上一个点(记录路径),路径中点的个数
string name;void dijkstra(int s)
{fill(dis,dis+maxn,inf);numweight[s]=0; //初始总点权cnt[s]=0;  //初始路径中点的个数（不算起点）dis[s]=0; //初始距离num[s]=1; //初始路径数pre[s]=-1; //起点的上一个顶点设置为-1aveweight[s]=0; //初始平均点权p.push(node(s,0)); //入队while(!p.empty()){int u&#p().v; //取出第一个点p.pop();if(vis[u]) continue;vis[u]=1;for(int i=0;i<g[u].size();i++){int v=g[u][i].v;int w=g[u][i].w;if(vis[v]==false){if(dis[v]>dis[u]+w) //路径可优化，其他值全部更新{dis[v]=dis[u]+w;cnt[v]=cnt[u]+1; //路径中点数增加numweight[v]=numweight[u]+weight[v];num[v]=num[u];pre[v]=u;}else if(dis[v]==dis[u]+w) //路径相等{num[v]+=num[u]; //路径个数更新if(numweight[v]<numweight[u]+weight[v])//最大点权和可以更新，其他(除路径长度)全部更新{cnt[v]=cnt[u]+1;//路径中点数增加numweight[v]=numweight[u]+weight[v];pre[v]=u;}else if(numweight[v]==numweight[u]+weight[v])//最大点权和也相等{double aveu=(numweight[u]+weight[v])*1.0/(cnt[u]+1);//通过u到v 的平均点权和double avev=numweight[v]*1.0/cnt[v];//不通过u到v 的平均点权和if(aveu>avev) //如果可以优化，更新其他内容{pre[v]=u;cnt[v]=cnt[u]+1;}}}p.push(node(v,dis[v])); //入队}}}
}int main()
{cin>>n>>k>>name;m1[name]=1; //起点m2[1]=name;for(int i=2;i<=n;i++){cin>>name>>weight[i];m1[name]=i; //地名 - 编号m2[i]=name; //编号 - 地名}string a,b;int cost;while(k--){cin>>a>>b>>cost;g[m1[a]].push_back(node(m1[b],cost)); //无向图g[m1[b]].push_back(node(m1[a],cost));}dijkstra(1);int ans=m1["ROM"];cout<<num[ans]<<" "<<dis[ans]<<" "<<numweight[ans]<<" "<<numweight[ans]/cnt[ans]<<endl;//输出路径数 ， 最短距离(花费) ， 最大点权和 ， 平均点权和vector<int> path; //存路径path.push_back(ans); //加入终点while(pre[ans]!=-1){path.push_back(pre[ans]); //不断加入前驱ans = pre[ans];}for(int i=path.size()-1;i>=0;i--) //倒着输出{cout<<m2[path[i]];if(i>=1) cout<<"->";}return 0;
}