给出一个无向图，一共n个节点，每条边有一个distance，问从节点1到n的所有路线中单条边distance的最小值是多少
题目保证一定有一条从1到n的路，所以就整个图从节点1开始BFS一遍，更新单条路的distance最小值
1 #2492
2 #Runtime: 1542 ms (Beats 70.59%)
3 #Memory: 73.7 MB (Beats 58.82%)
4
5 class Solution(object):
6 def minScore(self, n, roads):
7 """
8 :type n: int
9 :type roads: List[List[int]]
10 :rtype: int
11 """
12 edge = defaultdict(list)
13 ans = 0
14 for x, y, w in roads:
15 edge[x].append((y, w))
16 edge[y].append((x, w))
17 ans += w
18 q = deque([1])
19 vis = [0] * (n + 1)
20 vis[1] = 1
21 while q:
22 x = q.popleft()
23 for y, w in edge[x]:
24 if not vis[y]:
25 q.append(y)
26 vis[y] = 1
27 ans = min(ans, w)
28 return ans