結果

問題 No.1473 おでぶなおばけさん
コンテスト
ユーザー Craft Boss
提出日時 2025-10-03 21:23:38
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 5,996 bytes
コンパイル時間 1,858 ms
コンパイル使用メモリ 12,544 KB
実行使用メモリ 36,428 KB
最終ジャッジ日時 2025-10-03 21:23:45
合計ジャッジ時間 4,732 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other TLE * 1 -- * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

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)

# ２分探索で1からnに到達できる最大のwを求める
def findMax_w(roads, town_num):
    ok, ng = 0, roads[0][2]+1   #絶対ok/ngな初期値
    while ng-ok >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])  #初期位置の１だけを格納したキュー(FIFO)を作成
    """
    deque()
    デックと呼びリストの両端（先頭と末尾）での要素の追加や削除が非常に高速に行える、リストによく似たデータ構造
    キューやスタックのような構造にある両端からの追加、削除に向いている
    末尾に追加/削除 (append, pop): リストと同じく高速
    先頭に追加/削除 (appendleft, popleft): リストより高速。誰もズレる必要がない
    dequeを使うには、collectionsモジュールからimportする必要がある
    """
    distance = [-1] * (town_num + 1)    #それぞれの都市に到達できる最短距離のリスト。初期値は一度も行ったことがないことを表す-1
    distance[1] = 0 #スタート地点の都市１の距離は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()
0