https://pintia.cn/problem-sets/994805342720868352/problems/994805379664297984
PAT这种类型地题出了很多次了。
思路:
- 先将字符串映射到数字，数字映射到字符串。便于两者直接的查找。
- 跑一下Dijkstra
- dfs一下，走一下所有的最短路，维护题目所要求的信息。
#include<bits/stdc++.h>
using namespace std
;
const int N
=1e3+10;
int g
[N
][N
],w
[N
],dist
[N
],vis
[N
],n
,k
;
int idx
,st
,ed
;
int cnt
,max_happy
,avg_happy
;
string start
;
unordered_map
<string
,int>mp
;
unordered_map
<int,string
>hush
;
unordered_map
<int,int>path
,ans
;
vector
<int>ve
;
int get(string x
)
{if(mp
.count(x
)==0) mp
[x
]=++idx
;hush
[mp
[x
]]=x
;return mp
[x
];
}
void Dijkstra(int st
)
{memset(dist
,0x3f,sizeof dist
);dist
[st
]=0;for(int i
=0;i
<n
;i
++){int t
=-1;for(int j
=1;j
<=n
;j
++) if(!vis
[j
]&&(t
==-1 || dist
[j
]<dist
[t
])) t
=j
;vis
[t
]=1;for(int j
=1;j
<=n
;j
++) dist
[j
]=min(dist
[j
],dist
[t
]+g
[t
][j
]);}
}
void dfs(int u
,int fa
,int sum
,int len
)
{if(u
==ed
){cnt
++;if(sum
>max_happy
){max_happy
=sum
;avg_happy
=sum
/len
;ans
=path
;}else if(sum
==max_happy
&&sum
/len
>avg_happy
) {avg_happy
=sum
/len
,ans
=path
;}return;}for(int i
=1;i
<=n
;i
++){if(i
==fa
) continue;if(dist
[i
]==dist
[u
]+g
[u
][i
]) {path
[i
]=u
;dfs(i
,u
,sum
+w
[i
],len
+1);}}
}
int main(void)
{memset(g
,0x3f,sizeof g
);cin
>>n
>>k
>>start
;for(int i
=1;i
<=n
-1;i
++){string name
;int c
; cin
>>name
>>c
;int u
=get(name
);w
[u
]=c
;}for(int i
=1;i
<=k
;i
++){string x
,y
;int a
,b
,c
; cin
>>x
>>y
>>c
;a
=get(x
),b
=get(y
);g
[a
][b
]=g
[b
][a
]=min(g
[a
][b
],c
);}st
=get(start
),ed
=get("ROM");Dijkstra(st
);dfs(st
,-1,0,0);cout
<<cnt
<<" "<<dist
[ed
]<<" "<<max_happy
<<" "<<avg_happy
<<endl
;do{ve
.push_back(ed
);ed
=ans
[ed
];}while(ed
!=st
);cout
<<start
;for(int i
=ve
.size()-1;i
>=0;i
--) cout
<<"->"<<hush
[ve
[i
]];return 0;
}
总结
以上是生活随笔为你收集整理的1087 All Roads Lead to Rome (30 分)【难度: 一般 / Dijkstra】的全部内容，希望文章能够帮你解决所遇到的问题。
如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。
