【競技プログラミング】AtCoder Beginner Contest 373_D問題

# 問題
https://atcoder.jp/contests/abc373/tasks/abc373_d

# 問題イメージ
![base_image.create_20250420000807-ページ1.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/273b7221-23cf-40c4-afb2-d5b0800f99eb.png)


# 既存投稿一覧ページへのリンク
[一覧ページ](https://qiita.com/o_chan_t/items/fc759695acfaef8df2cc)

## Before
[AtCoder Beginner Contest 373_C 問題](https://qiita.com/o_chan_t/items/e09143408dc986e34877)


# 解法手順1
## 解法アプローチ

1. グラフの各頂点に値を割り当てる問題を、差分の制約を満たす問題として捉える。
2. 幅優先探索（BFS）を用いて、連結成分ごとに値を割り当てていく。
3. 未訪問の頂点から探索を開始し、隣接する頂点に対して差分の制約を満たすように値を割り当てる。
4. すべての頂点に値が割り当てられるまで、この処理を繰り返す。

## 解法手順

1. 入力を受け取り、グラフの構造を隣接リストとして保存する。各辺の重みも記録する。
2. 各頂点の値を格納する配列と、訪問済みを記録する配列を用意する。
3. 未訪問の頂点を見つけたら、その頂点に0を割り当て、BFSのキューに追加する。
4. キューから頂点を取り出し、隣接する未訪問の頂点に対して以下の処理を行う：
   - 現在の頂点との差分（辺の重み）を考慮して値を割り当てる。
   - 割り当てた頂点を訪問済みとしてマークし、キューに追加する。
5. キューが空になるまで4の処理を繰り返す。
6. すべての頂点が訪問済みになるまで、3-5の処理を繰り返す。
7. 最後に、各頂点に割り当てられた値を出力する。


# ACコード1
```python:ac.py
from collections import deque

def io_func():
    # 頂点数Nと辺数Mを入力として受け取る
    N, M = map(int, input().split())
    # 辺の情報を格納するリストを初期化
    edges = []
    for _ in range(M):
        # 各辺の情報（始点、終点、重み）を入力として受け取る
        u, v, w = map(int, input().split())
        edges.append((u-1, v-1, w))  # 0-indexedに調整
    return N, M, edges

def solve(N, M, edges):
    # 各頂点の値を格納する配列を初期化
    ans = [None] * N
    # 訪問済みを記録する配列を初期化
    visited = [False] * N
    # 隣接リストとして辺の情報を格納
    cost = [{} for _ in range(N)]
    
    # 辺の情報を隣接リストに変換
    for u, v, w in edges:
        cost[u][v] = w
        cost[v][u] = -w  # 逆方向の辺も追加
    
    # すべての頂点を処理
    for i in range(N):
        if ans[i] is not None:
            continue  # すでに値が割り当てられている場合はスキップ
        
        # 未訪問の頂点に0を割り当て
        ans[i] = 0
        visited[i] = True
        
        # 隣接する頂点がない場合はスキップ
        if len(cost[i]) == 0:
            continue
        
        # BFSのキューを初期化
        bfs = deque([(i, v) for v in cost[i].keys()])
        for j in cost[i].keys():
            visited[j] = True
        
        # BFSを実行
        while bfs:
            u, v = bfs.popleft()
            w = cost[u][v]
            
            # 差分の制約を満たすように値を割り当てる
            ans[v] = ans[u] + w
            
            # 隣接する未訪問の頂点をキューに追加
            for j in cost[v].keys():
                if not visited[j]:
                    bfs.append((v, j))
                    visited[j] = True
    
    # 結果を文字列として結合して返す
    return " ".join(map(str, ans))

# メイン処理
N, M, edges = io_func()
result = solve(N, M, edges)
print(result)

###
# N: 頂点の数
# M: 辺の数
# edges: 辺の情報を格納するリスト
# ans: 各頂点に割り当てられた値を格納する配列
# visited: 各頂点の訪問状態を記録する配列
# cost: 隣接リストとして辺の情報を格納する辞書のリスト
# bfs: 幅優先探索に使用するキュー

# 1. io_func関数:
#    - 標準入力から頂点数N、辺数M、各辺の情報を読み取る
#    - 辺の情報を0-indexedに調整して返す
# 2. solve関数:
#    - 入力された情報をもとにグラフを構築し、各頂点に値を割り当てる
#    - 幅優先探索（BFS）を用いて連結成分ごとに値を割り当てる
#    - 未訪問の頂点から探索を開始し、隣接する頂点に差分の制約を満たすように値を割り当てる
#    - すべての頂点に値が割り当てられるまで処理を繰り返す
#    - 最終的に各頂点に割り当てられた値を文字列として結合して返す
# 3. メイン処理:
#    - io_func関数を呼び出して入力を受け取る
#    - solve関数を呼び出して問題を解く
#    - 結果を標準出力に出力する
```
## オブジェクト指向版1
```python:ac_object.py
from collections import deque
import logging
from abc import ABC, abstractmethod

def setup_logger(debug_mode):
    logger = logging.getLogger(__name__)
    logger.setLevel(logging.DEBUG if debug_mode else logging.INFO)
    formatter = logging.Formatter('%(asctime)s - %(name)s - %(levelname)s - %(message)s')
    
    file_handler = logging.FileHandler('program_trace.log')
    file_handler.setFormatter(formatter)
    logger.addHandler(file_handler)
    
    return logger

# 入力ハンドラーの抽象クラス
class InputHandler(ABC):
    @abstractmethod
    def get_input(self):
        pass

# 標準入力ハンドラー
class StandardInputHandler(InputHandler):
    def get_input(self):
        # 頂点数Nと辺数Mを入力として受け取る
        N, M = map(int, input().split())
        # 辺の情報を格納するリストを初期化
        edges = []
        for _ in range(M):
            # 各辺の情報（始点、終点、重み）を入力として受け取る
            u, v, w = map(int, input().split())
            edges.append((u-1, v-1, w))  # 0-indexedに調整
        return N, M, edges

# 出力ハンドラーの抽象クラス
class OutputHandler(ABC):
    @abstractmethod
    def output_result(self, result):
        pass

# 標準出力ハンドラー
class StandardOutputHandler(OutputHandler):
    def output_result(self, result):
        print(result)

# グラフソルバー
class GraphSolver:
    def __init__(self, debug_mode=False):
        self.logger = setup_logger(debug_mode)

    def solve(self, N, M, edges):
        self.logger.debug(f"グラフソルバーの処理を開始します。N={N}, M={M}, edges={edges}")
        # 各頂点の値を格納する配列を初期化
        ans = [None] * N
        # 訪問済みを記録する配列を初期化
        visited = [False] * N
        # 隣接リストとして辺の情報を格納
        cost = [{} for _ in range(N)]
        
        # 辺の情報を隣接リストに変換
        for u, v, w in edges:
            cost[u][v] = w
            cost[v][u] = -w  # 逆方向の辺も追加
        
        self.logger.debug(f"隣接リストの構築が完了しました: {cost}")
        
        # すべての頂点を処理
        for i in range(N):
            if ans[i] is not None:
                self.logger.debug(f"# すでに値が割り当てられている(ans[{i}]=({ans[i]}))場合はスキップ")
                continue  # すでに値が割り当てられている場合はスキップ
            
            self.logger.debug(f"頂点 {i} の処理を開始します")
            
            # 未訪問の頂点に0を割り当て
            ans[i] = 0
            visited[i] = True
            
            # 隣接する頂点がない場合はスキップ
            if len(cost[i]) == 0:
                self.logger.debug(f"頂点 {i} には隣接する頂点がありません")
                continue
            
            # BFSのキューを初期化
            bfs = deque([(i, v) for v in cost[i].keys()])
            for j in cost[i].keys():
                visited[j] = True
            
            self.logger.debug(f"BFSキューの初期状態(頂点{i}の隣接点({cost[i].keys()})): {bfs}")
            self.logger.debug(f"visitedの状態: {visited}")
            
            # BFSを実行
            while bfs:
                u, v = bfs.popleft()
                w = cost[u][v]
                
                # 差分の制約を満たすように値を割り当てる
                ans[v] = ans[u] + w
                
                self.logger.debug(f"頂点 {v} に値 {ans[v]} を割り当てました")
                
                # 隣接する未訪問の頂点をキューに追加
                for j in cost[v].keys():
                    if not visited[j]:
                        bfs.append((v, j))
                        visited[j] = True
                        self.logger.debug(f"頂点 {j} をキューに追加しました")
        
        self.logger.debug(f"すべての頂点の処理が完了しました。結果: {ans}")
        
        # 結果を文字列として結合して返す
        return " ".join(map(str, ans))

# メイン処理を行うクラス
class GraphProblemSolver:
    def __init__(self, input_handler: InputHandler, output_handler: OutputHandler, solver: GraphSolver):
        self.input_handler = input_handler
        self.output_handler = output_handler
        self.solver = solver

    def solve(self):
        # 入力を取得
        N, M, edges = self.input_handler.get_input()
        # 問題を解く
        result = self.solver.solve(N, M, edges)
        # 結果を出力
        self.output_handler.output_result(result)

# メイン処理
if __name__ == "__main__":
    input_handler = StandardInputHandler()
    output_handler = StandardOutputHandler()
    solver = GraphSolver(debug_mode=True)  # デバッグモードを有効にする
    problem_solver = GraphProblemSolver(input_handler, output_handler, solver)
    problem_solver.solve()

```

### オブジェクト図
![fP91JiCm44NtESMe6nBHNC0Br1qWKK3q09QJZ58BnuuyOpRGkqCdI6c4Mo7ePXR_P-RzNs-8JUGqk68qxQlf4LRtVamCTyPtplf-1Uy5081fYADf6LfdY41Cui4eZkbt3JsojaUnh1Hm6XsAU2XaJ1_lsFZEnEwFIxAVrnyt2wZYKCoHdXB_8fEuiZn151sHakDo6Wg8OtK-t7-tvVP8JE7Cvx.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/530912/94b004a7-e676-b1e8-ae4a-ea9dfc6afa37.png)



### オブジェクト指向版1で書くメリット
#### 拡張性と再利用性
```python:ac_object.py
class FileInputHandler(InputHandler):
    def __init__(self, filename):
        self.filename = filename

    def get_input(self):
        with open(self.filename, 'r') as f:
            N, M = map(int, f.readline().split())
            edges = []
            for _ in range(M):
                u, v, w = map(int, f.readline().split())
                edges.append((u-1, v-1, w))
        return N, M, edges

class FileOutputHandler(OutputHandler):
    def __init__(self, filename):
        self.filename = filename

    def output_result(self, result):
        with open(self.filename, 'w') as f:
            f.write(result)

# メイン処理を変更
if __name__ == "__main__":
    input_handler = FileInputHandler("input.txt")
    output_handler = FileOutputHandler("output.txt")
    solver = GraphSolver(debug_mode=True)
    problem_solver = GraphProblemSolver(input_handler, output_handler, solver)
    problem_solver.solve()
```

#### テスト容易性
```python:ac_object.py
import unittest

class TestGraphSolver(unittest.TestCase):
    def setUp(self):
        self.solver = GraphSolver(debug_mode=True)

    def test_solve_simple_graph(self):
        N, M = 3, 3
        edges = [(0, 1, 2), (1, 2, 3), (2, 0, -5)]
        result = self.solver.solve(N, M, edges)
        self.assertEqual(result, "0 2 5")

    def test_solve_disconnected_graph(self):
        N, M = 4, 2
        edges = [(0, 1, 2), (2, 3, 3)]
        result = self.solver.solve(N, M, edges)
        self.assertEqual(result, "0 2 0 3")

if __name__ == '__main__':
    unittest.main()

```

# 独り言

この問題、グラフ問題だと思って問題文を読むと混乱するけど、普通の数学問題だと思って読むと納得行くか。

グラフ問題っぽい出題文は、解き方のヒントってことかな。