这题水的有点蛋疼。
题意
有N个城市,M条无向边。现在需要从某个给定的起始城市出发(除了起始城市外,其他每个城市都有一一个“幸福值”,前往名为“ROM”的城市。给出每条边所需要消耗的花费,求从起始城市出发,到达城市ROM所需要的最少花费,并输出最少花费的路径。如果这样的路径有多条,则选择路径上城市的“幸福值”之和最大的那条。如果路径仍然不唯一,则选择路径上城市的平均幸福值最大的那条。
思路
本题中的边权只有“花费”的概念,因此可以把它作为第一标尺,即把花费理解为距离。除了需要求解从起点到终点的最短距离外,还要求输出最短路径、最短路径条数、路径上的点权之和以及路径上的平均点权。如果有多条最短路径,则选择点权之和最大的一条;若点权之和相同,则选择平均点权最大的一条。
注意点
由于起始顶点的点权没有给出,因此计算平均点权时是不计算起始顶点的,数组num也应当初始化为0。
const int N=210;
unordered_map<string,int> mp;
vector<PII> g[N];
string city[N];
int happy[N];
int dist[N];
bool vis[N];
int f[N],cnt[N],num[N];
int pre[N];
int n,m;
void dijkstra()
{
memset(dist,0x3f,sizeof dist);
memset(pre,-1,sizeof pre);
priority_queue<PII,vector<PII>,greater<PII>> heap;
dist[1]=0;
f[1]=0;
num[1]=0;
cnt[1]=1;
heap.push({0,1});
while(heap.size())
{
int t=heap.top().se;
heap.pop();
if(vis[t]) continue;
vis[t]=true;
for(int i=0;i<g[t].size();i++)
{
int j=g[t][i].fi,w=g[t][i].se;
if(dist[j] > dist[t]+w)
{
dist[j]=dist[t]+w;
f[j]=f[t]+happy[j];
cnt[j]=cnt[t];
num[j]=num[t]+1;
pre[j]=t;
heap.push({dist[j],j});
}
else if(dist[j] == dist[t]+w)
{
cnt[j]+=cnt[t];
if(f[j] < f[t]+happy[j])
{
f[j]=f[t]+happy[j];
num[j]=num[t]+1;
pre[j]=t;
}
else if(f[j] == f[t]+happy[j] && num[j] > num[t]+1)
{
num[j]=num[t]+1;
pre[j]=t;
}
}
}
}
}
void print(int x)
{
if(x == 1)
{
cout<<city[1];
return;
}
print(pre[x]);
cout<<"->"<<city[x];
}
int main()
{
cin>>n>>m>>city[1];
mp[city[1]]=1;
for(int i=2;i<=n;i++)
{
cin>>city[i]>>happy[i];
mp[city[i]]=i;
}
while(m--)
{
string a,b;
int w;
cin>>a>>b>>w;
int ta=mp[a],tb=mp[b];
g[ta].pb({tb,w});
g[tb].pb({ta,w});
}
dijkstra();
int ed=mp["ROM"];
cout<<cnt[ed]<<' '<<dist[ed]<<' '<<f[ed]<<' '<<f[ed]/num[ed]<<endl;
print(ed);
//system("pause");
return 0;
}