Pagini recente » Cod sursa (job #2443619) | Cod sursa (job #18211) | Cod sursa (job #2263725) | Cod sursa (job #2788453) | Cod sursa (job #2489016)
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
return dfs(k, 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()