魔法师 (@Constanline) 在 Leetcode每日一题 —— 2492. 两个城市间路径的最小分数 中发帖

思路
题目里说 一条路径可以 多次 包含同一条道路，你也可以沿着路径多次到达城市 1 和城市 n 那么意味着最小距离是具有传染性的，节点联通的所有路径中的最小距离，就是这个连通图的最小分数。 
所以问题就变成了检查1所在的连通图中所有边的最小距离。而检查是否连通我们刚好有个适用的算法并查集~ 
遍历两遍roads，第一遍构造连通图，第二遍检查这条路径是否与1连通，如果连通更新最小分数。 
当然也可以在第一遍的时候把最小分数记录下来，第二遍遍历节点。 
代码
class Solution {
    private int[] parent;
    public int minScore(int n, int[][] roads) {
        // 并查集初始化
        parent = new int[n + 1];
        for (int i = 1; i...
 
 
Back to Top