PAT (Advanced Level) Practice - 1087 All Roads Lead to Rome（30 分）

#include<bits/stdc++.h>#include<cmath>#define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007usingnamespacestd;
typedeflonglongll;
constintmaxn=250;
intn,m,w,d;
// 幸福指数rs  幸福指数    记录访问   最短距离rs 路径记录   路径条数    结点个数intcst[maxn], cost[maxn], vis[maxn], dis[maxn], pre[maxn], path[maxn], vex[maxn];
intg[maxn][maxn];
strings,su,sv;
unordered_map<int,string>name;
unordered_map<string,int>id;
voidinit()
{
mem(dis,INF), mem(g,INF), mem(pre,-1);
mem(vis,0), mem(cost,0), mem(path,0), mem(vex,0), mem(cst,0);
}
intdijkstra(intv)
{
dis[v]=0, path[v]=1;
while(1)
    {
intmi=INF;
v=-1;
for(inti=1;i<=n;i++)
if(!vis[i] &&dis[i]<mi)
mi=dis[i], v=i;
if(v==d) return1;
if(v==-1) return0;
vis[v]=1;
for(inti=1;i<=n;i++)
        {
if(!vis[i] &&mi+g[v][i]<dis[i])
            {
dis[i]=mi+g[v][i];
cst[i]=cst[v]+cost[i];
path[i]=path[v];
vex[i]=1+vex[v];
pre[i]=v;
            }
elseif(!vis[i] &&mi+g[v][i]==dis[i])
            {
path[i]+=path[v];
if(cst[i]<cst[v]+cost[i])
                {
cst[i]=cst[v]+cost[i];
vex[i]=1+vex[v];
pre[i]=v;
                }
elseif(cst[i]==cst[v]+cost[i] &&vex[i]>vex[v]+1)
                {
vex[i]=vex[v]+1;
pre[i]=v;
                }
            }
        }
    }
}
intmain()
{
init();
scanf("%d%d",&n,&m), cin>>s;
name[1]=s, id[s]=1, cost[1]=0;
for(inti=2;i<=n;i++)
    {
cin>>su>>w;
name[i]=su, id[su]=i, cost[i]=w;
if(su=="ROM") d=i;
    }
for(inti=0;i<m;i++)
    {
cin>>su>>sv>>w;
g[id[su]][id[sv]]=g[id[sv]][id[su]]=w;
    }
if(dijkstra(id[s]))
    {
vector<int>vec;
printf("%d %d %d %d\n",path[d],dis[d],cst[d],int(cst[d]*1.0/vex[d]));
inth=d;
while(h!=-1)
        {
vec.push_back(h);
h=pre[h];
        }
for(inti=vec.size()-1;i>=0;i--)
printf("%s%s",name[vec[i]].c_str(),i==0?"\n":"->");
    }
elseputs("-1");
return0;
}