/**
* 求从1出发到n的路径中最短的一条边，1和n可以重复走，那么意味着只要1点和n点能到达的任何点相关的边都要统计，
* 即和1在一个连通块里面的所有边中最小的一个。
* 通过dfs从1点出发，枚举所有边。
**/
class Solution {
List<int[]>[] g;
boolean[] vis = new boolean[100005];
int ans = Integer.MAX_VALUE;
public int minScore(int n, int[][] roads) {
g = new ArrayList[n + 5];
Arrays.setAll(g, val->new ArrayList<>());
for (int[] e: roads) {
g[e[0]].add(new int[]{e[1], e[2]});
g[e[1]].add(new int[]{e[0], e[2]});
}
dfs(1);
return ans;
}
void dfs(int u) {
vis[u] = true;
for (int[] t : g[u]) {
int v = t[0], w = t[1];
ans = Math.min(ans, w);
if (!vis[v]) dfs(v);
}
}
}
class Solution:
def minScore(self, n: int, roads: List[List[int]]) -> int:
graph = defaultdict(list)
for u, v, d in roads:
graph[u].append((v, d))
graph[v].append((u, d))
que = deque()
que.append(1)
visited = set()
visited.add(1)
res = inf
while que:
u = que.popleft()
for v, d in graph[u]:
res = min(res, d)
if v not in visited:
visited.add(v)
que.append(v)
return res
func minScore(n int, roads [][]int) int {
type edge struct{ to, d int }
g := make([][]edge, n)
for _, e := range roads {
x, y, d := e[0]-1, e[1]-1, e[2]
g[x] = append(g[x], edge{y, d})
g[y] = append(g[y], edge{x, d})
}
ans := math.MaxInt32
vis := make([]bool, n)
var dfs func(int)
dfs = func(x int) {
vis[x] = true
for _, e := range g[x] {
ans = min(ans, e.d)
if !vis[e.to] {
dfs(e.to)
}
}
}
dfs(0)
return ans
}
func min(a, b int) int { if a > b { return b }; return a }
# 由于路径可以折返，取连通块中的 idistance i最小的那条边，即为答案。
class Solution:
def minScore(self, n: int, roads: List[List[int]]) -> int:
g = [[] for _ in range(n)]
for x, y, d in roads:
g[x - 1].append((y - 1, d))
g[y - 1].append((x - 1, d))
ans = inf
vis = [False] * n
def dfs(x: int) -> None:
nonlocal ans
vis[x] = True
for y, d in g[x]:
ans = min(ans, d)
if not vis[y]:
dfs(y)
dfs(0)
return ans
