本文共 1470 字，大约阅读时间需要 4 分钟。

题目链接：

题目大意：略。

解题思路：经典。

AC 代码

#include
   
    #include
    
     #define mem(a,b) memset(a,b,sizeof a)#define ssclr(ss) ss.clear(), ss.str("")#define INF 0x3f3f3f3f#define MOD 1000000007using namespace std;typedef long long ll;const int maxn=250;int n,m,w,d;// 幸福指数rs  幸福指数    记录访问   最短距离rs 路径记录   路径条数    结点个数int cst[maxn], cost[maxn], vis[maxn], dis[maxn], pre[maxn], path[maxn], vex[maxn];int g[maxn][maxn];string s,su,sv;unordered_map
     
       name;unordered_map
      
        id;void init(){    mem(dis,INF), mem(g,INF), mem(pre,-1);    mem(vis,0), mem(cost,0), mem(path,0), mem(vex,0), mem(cst,0);}int dijkstra(int v){    dis[v]=0, path[v]=1;    while(1)    {        int mi=INF;        v=-1;        for(int i=1;i<=n;i++)            if(!vis[i] && dis[i]
       
        vex[v]+1)                {                    vex[i]=vex[v]+1;                    pre[i]=v;                }            }        }    }}int main(){    init();    scanf("%d%d",&n,&m), cin>>s;    name[1]=s, id[s]=1, cost[1]=0;    for(int i=2;i<=n;i++)    {        cin>>su>>w;        name[i]=su, id[su]=i, cost[i]=w;        if(su=="ROM") d=i;    }    for(int i=0;i
        
         >su>>sv>>w; g[id[su]][id[sv]]=g[id[sv]][id[su]]=w; } if(dijkstra(id[s])) { vector
         
           vec; printf("%d %d %d %d\n",path[d],dis[d],cst[d],int(cst[d]*1.0/vex[d])); int h=d; while(h!=-1) { vec.push_back(h); h=pre[h]; } for(int i=vec.size()-1;i>=0;i--) printf("%s%s",name[vec[i]].c_str(),i==0?"\n":"->"); } else puts("-1"); return 0;}
         
        
       
      
     
    
   

转载地址：https://lux-sun.blog.csdn.net/article/details/82116117 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！