Problem p03450 (python)

Fixed submission:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def main():
    n, m = map(int, sys.stdin.readline().split())
    lrds = ((map(int, line.split())) for line in sys.stdin.readlines())

    g = tuple([] for _ in range(n))
    x = [None] * n

    for l, r, d in lrds:
        l -= 1
        r -= 1
        g[l].append((r, d))
        g[r].append((l, -d))

    for i in range(n):
        if x[i] is not None:
            continue
        stack = [i]
        x[i] = 0
        while len(stack):
            v = stack.pop()
            for u, d in g[v]:
                if x[u] is None:
                    stack.append(u)
                    x[u] = x[v] + d

    for v in range(n):
        for u, d in g[v]:
            if x[v] + d != x[u]:
                print('No')
                sys.exit()

    print('Yes')

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
amnesia@amnesia:~/Persistent/procon/atcoder/abc/087$ cat d2.py 
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def dist(a, l, r):
    st = [(l, 0)]
    while len(st) > 0:
        i, d = st.pop()
        if i == r:
            return d

        if r in a[i]:
            d += a[i][r]
            a[l][r] = d
            st.append((r, d))
            continue

        for k, v in a[i].items():
            d += v
            a[l][k] = d
            st.append((k, d))

    return -1


def main():
    (n, m) = tuple(map(int, input().split()))
    a = {i:{} for i in range(1, n + 1)}
    for line in sys.stdin:
        (l, r, d) = map(int, line.split())
        pd = dist(a, l, r)
        if pd != -1 and pd != d or dist(a, r, l) != -1:
            print('No')
            sys.exit()
        a[l][r] = d

    print('Yes')

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def dist(h, l, r):
    st = [(l, 0)]
    while len(st) > 0:
        i, d = st.pop()
        if i == r:
            break
        if not h[i][r]:
            st.append((r, d + h[i][r]))
            continue
        for j in range(r):
            if not h[i][j] or i == j:
                continue
            st.append((j, d + h[i][j]))

    return st[-1] if len(st) > 0 else -1


def main():
    (n, m) = tuple(map(int, input().split()))
    lrds = tuple(map(int, input().split()) for _ in range(m))

    h = [[None] * n] * n
    for lrd in lrds:
        (l, r, d) = lrd
        if not h[l][l]:
            h[l][l] = 0
        if not st[r][r]:
            h[r][r] = 0
        pd = dist(h, l, r)
        if pd != -1 and pd != d:
            print('No')
            sys.exit()
        h[l][r] = d
        h[r][l] = -d

    print('Yes')

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

def dist(h, l, r):
    st = [(l, 0)]
    while len(st) > 0:
        i, d = st.pop()
        if i == r:
            break
        if not h[i][r]:
            st.append((r, d + h[i][r]))
            continue
        for j in range(r):
            if not h[i][j] or i == j:
                continue
            st.append((j, d + h[i][j]))

    return st[-1] if len(st) > 0 else 0


def main():
    (n, m) = tuple(map(int, input().split()))
    lrds = tuple(map(int, input().split()) for _ in range(m))

    h = [[None] * n] * n
    for lrd in lrds:
        (l, r, d) = lrd
        if not h[l][l]:
            h[l][l] = 0
        if not st[r][r]:
            h[r][r] = 0
        pd = dist(h, l, r)
        if pd != -1 and pd != d:
            print('No')
            sys.exit()
        h[l][r] = d
        h[r][l] = -d

    print('Yes')

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

sys.setrecursionlimit(10000)

class G(object):
    def __init__(self, i):
        self.paths = dict()

    def add(self, v, d):
        self.paths[v] = d

    def dist(self, g, s):
        if self is g:
            return s
        if g in self.paths:
            d = g.dist(g, s + self.paths[g])
            self.add(g, d)
            return d
        for k, v in self.paths.items():
            d = k.dist(g, s + v)
            if d >= 0:
                self.add(v, d)
                return d
        return -1

def main():
    (n, m) = tuple(map(int, input().split()))
    lrds = tuple(map(int, input().split()) for _ in range(m))

    g = dict()
    for lrd in lrds:
        (l, r, d) = lrd
        if l not in g:
            g[l] = G(l)
        if r not in g:
            g[r] = G(r)
        pd = g[l].dist(g[r], 0)
        if pd != -1 and pd != d or g[r].dist(g[l], 0) != -1:
            print('No')
            sys.exit()
        g[l].add(g[r], d)

    print('Yes')

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

class G(object):
    def __init__(self, i):
        self.paths = dict()

    def add(self, v, d):
        self.paths[v] = d

    def dist(self, g, s):
        if self is g:
            return s
        if g in self.paths:
            d = g.dist(g, s + self.paths[g])
            self.add(g, d)
            return d
        for k, v in self.paths.items():
            d = k.dist(g, s + v)
            if d >= 0:
                self.add(v, d)
                return d
        return -1

def main():
    (n, m) = tuple(map(int, input().split()))
    lrds = tuple(map(int, input().split()) for _ in range(m))

    g = dict()
    for lrd in lrds:
        (l, r, d) = lrd
        if l not in g:
            g[l] = G(l)
        if r not in g:
            g[r] = G(r)
        pd = g[l].dist(g[r], 0)
        if pd != -1 and pd != d or g[r].dist(g[l], 0) != -1:
            print('No')
            sys.exit()
        g[l].add(g[r], d)

    print('Yes')

if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
#!/usr/bin/python3
# -*- coding: utf-8 -*-

import sys

class G(object):
    def __init__(self, i):
        self.i = i
        self.a = []

    def add(self, v, d):
        self.a.append((v, d))

    def path(self, j, s):
        if self.i == j:
            return s
        for v in self.a:
            d = v[0].path(j, s + v[1])
            if d >= 0:
                return d
        return -1

def main():
    n, m = tuple(map(int, input().split()))
    lrds = tuple(map(int, input().split()) for _ in range(m))

    g = dict()
    for lrd in lrds:
        (l, r, d) = lrd
        if l not in g:
            g[l] = G(l)
        if r not in g:
            g[r] = G(r)
        pd = g[l].path(r, 0)
        if pd != -1 and pd != d or g[r].path(l, 0) != -1:
            print('No')
            sys.exit()
        g[l].add(g[r], d)

    print('Yes')

if __name__ == '__main__':
    main()