from collections import deque # 町の連結関係をparentで管理するクラス class TownConnectivity: # クラスの初期化(コンストラクタ) def __init__(self, town_num): """ オブジェクト作成時に、町の数に応じてparent配列を初期化する。 """ self.parent = [-1]*(town_num+1) # parent配列を-1で初期化 (各町が独立したグループ) # self.xxx とすることで、このオブジェクト固有の変数になる # 都市town_idが属するグループのリーダーを見つける def find(self, town_id): if self.parent[town_id]<0: return town_id else: self.parent[town_id]=self.find(self.parent[town_id]) return self.parent[town_id] # 都市sとtを連結させる def union(self, s, t): s_root= self.find(s) t_root= self.find(t) if s_root==t_root: return #属するメンバーが多いグループに少ないグループを属させる if self.parent[s_root]>self.parent[t_root]: # 属するメンバーの数は負の数 s_root, t_root = t_root, s_root self.parent[s_root] += self.parent[t_root] self.parent[t_root] = s_root # 2つの町aとbが連結しているかを手軽に確認 def is_connected(self, a, b): return self.find(a) == self.find(b) # w_min以上の耐久がある道だけを使ったmapを作成 def make_map(self, roads, w_min): i = 0 while i < len(roads) and roads[i][2] >= w_min: self.union(roads[i][0], roads[i][1]) i += 1 # 確認用 def printmap(self): print(self.parent) # 2分探索で1からnに到達できる最大のwを求める # 2分探索で1からnに到達できる最大のwを求める def findMax_w(roads, town_num): ok, ng = 0, roads[0][2]+1 #絶対ok/ngな初期値 while ng-ok >1: #到達可能だった重さと到達不可能だった重さの差が1になるまで繰り返し mid= (ok+ng)//2 #union-findを用いて1からnに到達可能か調べる conectivity = TownConnectivity(town_num) conectivity.make_map(roads, mid) if conectivity.is_connected(1, town_num): #w=midで到達可能の時 ok = mid else: #w=midで到達不可能の時 ng = mid return ok # 辺リストからmax_w以上の道だけを使った隣接リストに変換 def convertEdgeToAdjacency(roads, town_num, max_w): """ 隣接リスト 都市ごとに道でつながった隣接都市をセット化 """ adList = [set() for _ in range(town_num + 1)] #都市ごとに空のセットを用意 i = 0 for s, t, w in roads: #max_w以下の道でつながったいるそれぞれの都市のセットに相互の都市を追加 if w >= max_w: adList[s].add(t) adList[t].add(s) else: break return adList # BFSで最大w以上の道だけを使った最短経路を求める def findShortestPath(roads, town_num, max_w): roads = convertEdgeToAdjacency(roads, town_num, max_w) #roadsを隣接リストに queue = deque([1]) #初期位置の1だけを格納したキュー(FIFO)を作成 """ deque() デックと呼びリストの両端(先頭と末尾)での要素の追加や削除が非常に高速に行える、リストによく似たデータ構造 キューやスタックのような構造にある両端からの追加、削除に向いている 末尾に追加/削除 (append, pop): リストと同じく高速 先頭に追加/削除 (appendleft, popleft): リストより高速。誰もズレる必要がない dequeを使うには、collectionsモジュールからimportする必要がある """ distance = [-1] * (town_num + 1) #それぞれの都市に到達できる最短距離のリスト。初期値は一度も行ったことがないことを表す-1 distance[1] = 0 #スタート地点の都市1の距離は0 while queue: #queueの中身がなくなるまで繰り返す current_town = queue.popleft() #左から現在の位置を取り出す。これにより、先に入れたもの(より近い町)から探索するFIFO。 if town_num in roads[current_town]: #現在の都市から行ける都市の中にゴールが含まれていたら終了 return distance[current_town]+1 for neighbor in roads[current_town]: """ 現在の都市から行ける都市を一つずつ格納する その都市が行ったことあれば(distance!=-1)何もしない 行ったことない都市であればその都市への距離は現在いる都市までの距離+1 その都市を次に探索するキューの最後に追加 """ if distance[neighbor] == -1: distance[neighbor] = distance[current_town] + 1 queue.append(neighbor) # 実際の処理をmain関数にまとめる def main(): town_num, road_num = map(int, input().split()) # 辺リストで全ての道を保存 roads = [] for i in range(road_num): s, t, w = map(int, input().split()) roads.append((s, t, w)) # roadsをwについての降順に並び替え roads.sort(key=lambda x:x[2], reverse=True) """ key=:何を基準に並び替えるか指定 lambda 一時的にしか使わないなもなき関数を作成 x:x[2]: xが引数 (s, t, w)を格納 x[2]が戻り値 wを返す reverse=True:降順を指定。指定しないと昇順 """ max_w = findMax_w(roads, town_num) min_path = findShortestPath(roads, town_num, max_w) print(max_w, min_path) # このファイルが直接実行された時だけmain()を呼び出す if __name__ == "__main__": main()