給出一個(gè)無(wú)向圖，一共n個(gè)節(jié)點(diǎn)，每條邊有一個(gè)distance，問(wèn)從節(jié)點(diǎn)1到n的所有路線中單條邊distance的最小值是多少
題目保證一定有一條從1到n的路，所以就整個(gè)圖從節(jié)點(diǎn)1開(kāi)始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