Categorygithub.com/szhou12/leetcode-goleetcode2492-Minimum-Score-of-a-Path-Between-Two-Cities
package
0.0.0-20241220224003-b7cf03a90b2b
Repository: https://github.com/szhou12/leetcode-go.git
Documentation: pkg.go.dev
Overview
Dependencies
1
Dependents
0

# README

2492. Minimum Score of a Path Between Two Cities

Solution idea

Union Find

要点总结

  1. 注意题目一个重要的前提条件：一条边或一个节点可以重复多次访问。这意味着，我们可以特意"绕远路"只为了找到最短的那条边。这样问题可以转化为 :arrow_right: city 1 与 city N 之间的score本质，就是这两个节点所在连通图里最短的边
  2. 解题步骤:
    1. 用Union Find将所有的节点标记联通，将所有节点归到所属的连通图 (集合) 里
    2. 再遍历一遍所有的边，找到 city 1 (or city N) 所属连通图的节点以及对应的最短的边

Resource

【每日一题】LeetCode 2492. Minimum Score of a Path Between Two Cities