81 lines
2.1 KiB
Python
81 lines
2.1 KiB
Python
print(
|
||
"task: Graf10\nПоиск всех маршрутов между городами с сортировкой по длине и лексикографически"
|
||
)
|
||
|
||
import random
|
||
|
||
|
||
def create_file():
|
||
n = random.randint(4, 6)
|
||
with open("FileName1", "w") as f:
|
||
f.write(str(n) + "\n")
|
||
for i in range(n):
|
||
row = [str(random.randint(0, 1)) for _ in range(n)]
|
||
f.write(" ".join(row) + "\n")
|
||
|
||
|
||
def read_graph():
|
||
try:
|
||
with open("FileName1") as f:
|
||
n = int(f.readline())
|
||
m = [list(map(int, f.readline().split())) for _ in range(n)]
|
||
return n, m
|
||
except:
|
||
return None, None
|
||
|
||
|
||
def dfs(m, v, target, visited, path, all_paths):
|
||
if v == target:
|
||
all_paths.append(path[:])
|
||
return
|
||
for u in range(len(m)):
|
||
if m[v][u] == 1 and u not in visited:
|
||
visited.add(u)
|
||
path.append(u)
|
||
dfs(m, u, target, visited, path, all_paths)
|
||
path.pop()
|
||
visited.remove(u)
|
||
|
||
|
||
def solve(n, m, k1, k2):
|
||
paths = []
|
||
dfs(m, k1, k2, {k1}, [k1], paths)
|
||
paths.sort(key=lambda x: (len(x), x))
|
||
return paths
|
||
|
||
|
||
def write(paths):
|
||
with open("FileName2", "w") as f:
|
||
if not paths:
|
||
f.write("-1\n")
|
||
else:
|
||
f.write(str(len(paths)) + "\n")
|
||
for p in paths:
|
||
f.write(" ".join(str(x + 1) for x in p) + "\n")
|
||
|
||
|
||
while True:
|
||
print("\n1 - создать файл FileName1")
|
||
print("2 - выполнить задачу (результат в FileName2)")
|
||
print("0 - выход")
|
||
c = input(">> ")
|
||
if c == "1":
|
||
create_file()
|
||
print("FileName1 создан")
|
||
elif c == "2":
|
||
n, m = read_graph()
|
||
if n is None:
|
||
print("ошибка чтения FileName1")
|
||
continue
|
||
try:
|
||
k1 = int(input("K1: ")) - 1
|
||
k2 = int(input("K2: ")) - 1
|
||
except:
|
||
print("ошибка ввода")
|
||
continue
|
||
paths = solve(n, m, k1, k2)
|
||
write(paths)
|
||
print("результат записан в FileName2")
|
||
elif c == "0":
|
||
break
|