Решить 2 олимпиадные задачки на теорию графов
1. Таблица
Вам дана таблица n×n, где каждый квадрат содержит целое число от 1 до n×n.
Путь в таблице начинается с некоторого квадрата и всегда идет либо по вертикали, либо по горизонтали в другой квадрат с меньшим номером, чем текущий квадрат. Квадраты не обязательно должны быть соседними, и путь может состоять только из одного квадрата.
Сколько различных путей в таблице? Поскольку ответ может быть большим, выведите его остаток при делении ответа на 10^9+7.
Входные данные:
Первая строка содержит целое число n: размер сетки.
Следующие n строк содержат по n целых чисел: содержимое сетки.
Выходные данные:
Выведите одно целое число: количество путей по модулю 10^9+7.
Пример:
Входные данные:
3
2 1 3
1 1 1
9 2 7
Выходные данные:
46
Объяснение: В этом примере возможны, среди прочего, следующие три пути.
2.
Вам даны n городов, которые соединены друг с другом n−1 дорогами (т. е. города и дороги образуют граф, представляющий собой дерево). В каждом городе есть либо поле, либо порт.
Скоро сезон сбора урожая, и ваша задача — найти кратчайший путь от каждого поля до порта. Какова общая протяженность этих путей?
Входные данные
В первой строке записано целое число n: количество городов. Города пронумерованы от 1 до n включительно.
Вторая строка содержит n целых чисел t1, t2, … ,tn. Если число ti равно 0, то в городе i есть порт, а если число равно 1, то в городе i есть поле. Гарантируется, что хотя бы в одном городе есть порт.
Каждая из следующих n−1 строк содержит три целых числа a, b, c: между городами a и b есть дорога длиной c.
Выходные данные
Выведите одно целое число: суммарную длину кратчайших путей.
Пример
Входные данные:
6
1 1 0 0 1 1
1 2 20
2 3 30
2 5 50
3 6 60
1 4 10
Выходные данные:
180
Объяснение: Следующий рисунок соответствует примеру ввода.