Cod sursa(job #2489070)

Utilizator AlexandraaaaMereu Alexandra Alexandraaaa Data 7 noiembrie 2019 21:40:54
Problema Sate Scor 15
Compilator py Status done
Runda Arhiva de probleme Marime 1.07 kb
G = {}
x = 0
y = 0
viz = []

def read_file(file_name):
  global n, x, y, G, viz
  with open(file_name) as f:
    n, m, x, y = [int(x) for x in next(f).split()]
    for i in range(1, n+1):
      G[i] = {}

    for line in f:
      i, j, d = [int(x) for x in line.split()]
      G[i].update({j: d})
      G[j].update({i: -d})


def bfs():
  global x, y, G, viz

  q = [(x, 0)]

  while len(q):
    (node, dist) = q.pop(0)

    for k in G[node]:
      if not viz[k]:
        d = dist + G[node][k]

        if k == y:
          return d
        viz[k] = 1
        q.append((k, d))

  return 0


def dfs(node, dist):
  global x, y, G, viz

  viz[node] = 1
  for k in G[node]:
    if not viz[k]:
      d = dist + G[node][k]

      if k == y:
        return d
      d = dfs(k, d)
      if d:
        return d

  return 0

def write_file(file_name, res):
  with open('sate.out', 'w') as f:
    f.write(str(res))
  # print(res)


def main():
  global viz, n, x
  read_file("sate.in")
  viz = [0] * (n+1)
  # res = bfs()
  res = dfs(x, 0)
  write_file("sate.out", res)


if __name__ == "__main__":
  main()