2492. Circular Sentence

题目 #

You are given a positive integer n representing n cities numbered from 1 to n. You are also given a 2D array roads where roads[i] = [ai, bi, distancei] indicates that there is a bidirectional road between cities ai and bi with a distance equal to distancei. The cities graph is not necessarily connected.

The score of a path between two cities is defined as the minimum distance of a road in this path.

Return the minimum possible score of a path between cities 1 and n.

Note:

  • A path is a sequence of roads between two cities.
  • It is allowed for a path to contain the same road multiple times, and you can visit cities 1 and n multiple times along the path.
  • The test cases are generated such that there is at least one path between 1 and n.

Example 1:

Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]]
Output: 5
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 4. The score of this path is min(9,5) = 5.
It can be shown that no other path has less score.

Example 2:

Input: n = 4, roads = [[1,2,2],[1,3,4],[3,4,7]]
Output: 2
Explanation: The path from city 1 to 4 with the minimum score is: 1 -> 2 -> 1 -> 3 -> 4. The score of this path is min(2,2,4,7) = 2.

  Constraints:

  • $2 <= n <= 10^5$
  • $1 <= roads.length <= 10^5$
  • roads[i].length == 3
  • $1 <= a_i, b_i <= n$
  • $a_i != b_i$
  • $1 <= distancei <= 10^4$
  • There are no repeated edges.
  • There is at least one path between 1 and n.

思路1 并查集 #

分析 #

  • 读清楚题目，其实就是找从1出发的所有连通路上的最短的路
  • 本身就是两个思路bfs和并查集
  • 并查集在这里就是找到所有的和1在一条连通路的点，然后从道路中找到这些点的最短道路

代码 # 

 1type unionFind struct {
 2	parent []int
 3}
 4
 5func initUnionFind(n int) unionFind {
 6	u := unionFind{}
 7	u.parent = make([]int, n)
 8	for i := range u.parent {
 9		u.parent[i] = i
10	}
11	return u
12}
13
14func (u unionFind) find(a int) int {
15	ap := u.parent[a]
16	// 找到最终节点
17	for ap != u.parent[ap] {
18		ap = u.parent[ap]
19	}
20	// 沿途都赋值最终节点
21	for a != ap {
22		u.parent[a], a = ap, u.parent[a]
23	}
24	return ap
25}
26
27func (u unionFind) merge(a, b int) {
28	// b的父节点等于a的父节点，就是将两个点合并
29	u.parent[u.find(b)] = u.find(a)
30}
31
32func min(a, b int) int {
33	if b < a {
34		return b
35	}
36	return a
37}
38
39func minScore(n int, roads [][]int) int {
40	union := initUnionFind(n + 1)
41	for _, v := range roads {
42		x, y := v[0], v[1]
43		// 建立关系
44		union.merge(x, y)
45	}
46	result := math.MaxInt
47	for _, item := range roads {
48		x, v := item[0], item[2]
49		// 如果点和第一个点有关系代表能到达，那么就看路径是不是最小
50		if union.find(x) == union.find(1) {
51			result = min(result, v)
52		}
53	}
54	return result
55}

思路2 bfs #

思路 #

  • 使用bfs将所有路都走一边，然后从能走到所有节点中找到连接的最短路径