Мне было трудно понять вашу программу.Итак, я переписал его, и я думаю, что мою версию немного легче понять.
import sys
import numpy as np
line = raw_input()
max_val, num_paths = (int(n) for n in line.split())
# a will be a list of tuples of int, taken from the input.
#
# Each tuple represents a path, so this is effectively a sparse representation
# of a square matrix of possible paths.
#
# Input city numbers are 1-based, but we will treat them as 0-based, so
# subtract 1 from each value before appending to array a.
a = []
for _ in xrange(num_paths):
line = raw_input()
# TRICKY: subtract 1 to convert from 1-based to 0-based city numbers
tup = tuple(int(n)-1 for n in line.split())
if len(tup) != 2:
raise ValueError, "input should only have two values per line"
for n in tup:
if not 0 <= n < max_val:
raise ValueError, "value must be in range [1, %d]" % max_val
if tup[0] >= tup[1]:
#raise ValueError, "INFINITE PATHS"
print "INFINITE PATHS"
sys.exit(0)
a.append(tup)
# Expand the sparse matrix representation into an actual square matrix.
# It should have a 1 anywhere a path was indicated with a tuple in list a,
# and a 0 everywhere else.
b = [ [0 for _ in xrange(max_val)] for _ in xrange(max_val)]
for i, j in a:
b[i][j] = 1
c = 0
for i in xrange(num_paths):
d = np.linalg.matrix_power(b, i + 1)
c += d[0][max_val - 1]
print c
Моя версия печатает 2, когда приводится пример ввода.
Вот некоторые вещиЯ понял, как я работал над этим:
Первая строка дает нам константы (N и M в документации, представляющие максимальное допустимое значение и количество путей соответственно).Вы должны сохранять эти значения в переменных с хорошими именами, а не помещать их в список и ссылаться на них по индексу списка.Я использовал имена max_val и num_paths.Вы сами допустили ошибку: вы должны найти пути из города 1 в город N, поэтому проверка в конце должна быть d[0][max_val - 1];Вы использовали l[1], который num_paths, а не l[0].
b должен быть квадратной матрицей.Ваш код устанавливал ширину на основе длины a, но max_val и num_paths не всегда могут быть равны, поэтому это опасный способ сделать это.
Странно зацикливатьсякаждую возможную точку в квадратной матрице и проверьте, должна ли она быть установлена в 1 или нет.Это также очень неэффективно, особенно потому, что тест in равен O (n), где n - длина массива a.Вместо этого создайте пустую квадратную матрицу, а затем просто зациклите пути и установите значения 1 для пути.
Аналогично, странно проверять входные значения в цикле, который инициализирует квадратную матрицу;лучше проверять входные значения по мере их чтения в цикле ввода.И снова это опасно, потому что num_paths может быть не связано с max_val.Также это неэффективно, потому что вы проверяли a[i-1][0] против a[i-1][1] один раз для столбца в b;это сравнение не использует значение j вообще.Вы делали каждую проверку пять раз;достаточно сделать каждую проверку по одному разу.
Существует идиома Python, которую я использовал, где вы можете использовать _ (единственное подчеркивание) в качестве имени переменной, если вам не важно значениеэтой переменной.Когда мы просто делаем что-то определенное количество раз с циклом и не будем использовать значение счетчика цикла ни для чего, я использовал _ в качестве переменной счетчика цикла.Это, конечно, не обязательно.
Чтобы ответить на ваш актуальный вопрос: я не вижу возможности для вашей программы не производить вывод.Я подозреваю, что может быть проблема на сервере, на котором выполняется эта тестовая проблема.Ваша программа всегда должна печатать «БЕСКОНЕЧНЫЕ ПУТИ» или какое-то целочисленное значение.
PS На самом деле я не понимаю, как работает ваша программа;в описании проблемы сказано, что вы должны указать несколько путей по модулю 1e9, и я не вижу ничего, что могло бы обеспечить это.