ABC373Dを解いた

以前ABCで解けなかった以下の問題を解いていく

実装コード

まず適当な値を最初のノードに入れ
そこから深さ優先探索をして、エッジの重みから
次のノードの値を計算する。

どうやら入力で与えられる
u→vの重みがwのエッジの他に
v→uで重みが-wのエッジを追加しても良いらしい

import sys
from collections import deque,defaultdict
def rI(): return int(sys.stdin.readline().rstrip())
def rLI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def rI1(): return (int(sys.stdin.readline().rstrip())-1)
def rLI1(): return list(map(lambda a:int(a)-1,sys.stdin.readline().rstrip().split()))
def rS(): return sys.stdin.readline().rstrip()
def rLS(): return list(sys.stdin.readline().rstrip().split())
def err(*args): print(*args, file=sys.stderr)

class Node:
    def __init__(self, val):
        self.val = val
        self.links = []

class Edge:
    def __init__(self, src, dest, wt):
        self.src = src
        self.dest = dest
        self.wt = wt

class Graph:
    def __init__(self, directed=False):
        self.nodes = {}
        self.directed = directed

    def __getitem__(self, k):
        return self.nodes[k]
    
    def __len__(self):
        return len(self.nodes)
    
    def add_node(self, val):
        node = Node(val)
        self.nodes[val] = node
    
    def add_edge(self, src, dest, wt):
        edge = Edge(src, dest, wt)
        if src not in self.nodes:
            self.add_node(src)
        if dest not in self.nodes:
            self.add_node(dest)
        self.nodes[src].links.append(edge)
        if not self.directed:
            reverse_edge = Edge(dest, src, -wt)
            self.nodes[dest].links.append(reverse_edge)
               
def main():
    N, M = rLI()
    G = Graph()

    for i in range(N):
        G.add_node(i+1)
    for _ in range(M):
        u, v, w = rLI()
        G.add_edge(u,v,w)    
    visited = set()
    result = defaultdict(lambda:None)
    # result[1] = {3:3,4:5,5:200401298}.get(len(G),0)

    for k in range(1,N+1):
        if k in visited: continue
        st = deque([G.nodes[k]])
        while st:
            node = st.pop()
            i = node.val
            visited.add(i)
            if result[i] is None:
                result[i] = 0
                # result[i] = (x:={4:6,5:278499365}.get(len(G),0))
                # err(i,x)
            for edge in node.links:
                d = G[edge.dest]
                if (j:=d.val) not in visited:
                    visited.add(j)
                    st.append(d)
                    if result[j] is None:
                        w = edge.wt + result[i]
                        result[j] = w
                        # err(j, w, edge.wt, result[i])
    
    ans = [result[i+1] for i in range(N)]
    print(*ans)
    
if __name__ == '__main__':
    main()

まとめ

ABC373Dを解いた、実装には深さ優先探索を使用した

感想

グラフの拒絶反応を克服するために問題を解いた、
なかなか難しいが、鉄則本を読みながらコーディングして、
グラフについて少し理解を進められた。