Задача №3862. msk.spring.2006.7C: гном
Как-то раз гному Кварку попала в руки карта сокровищ. На карте отмечено \(N\) точек, в которых может находиться клад. Все точки пронумерованы числами от \(1\) до \(N\). Для каждой пары точек Кварк знает длину дороги, их соединяющей. Свои поиски Кварк начинает от точки с номером \(1\). Прежде чем начать свой долгий путь, хитрый гном вычеркивает точки, в которых, по его мнению, клада быть не может. Гарантируется, что точка с номером \(1\) никогда не бывает вычеркнута. После этого Кварк выбирает некоторый маршрут, проходящий через все оставшиеся на карте точки. Маршрут не проходит через одну и ту же точку более одного раза. Кварк может ходить только по дорогам, соединяющим невычеркнутые точки.
Кварк хочет выбрать маршрут минимальной длины. Необходимо найти такой маршрут для Кварка.
В первой строке находится одно целое число \(N\) \((1 \lt N \le 15)\) — количество точек, отмеченных на карте. В последующих \(N\) строках находятся расстояния между точками. В \((i + 1)\)-й строке находятся \(N\) целых чисел \(d_{i1},\, d_{i2},\, \ldots,\, d_{iN}\) — длины дорог от \(i\)-й точки до всех остальных. Гарантируется, что \(d_{ij} = d_{ji}\), \(d_{ii} = 0\) и \(0 \lt d_{ij} \lt 100\). В \((N + 2)\)-й строке находится одно целое число \(Q\) \((1 \lt Q \le 1000)\) — количество вариантов вычеркивания точек для данной карты. В последующих \(Q\) строках содержится описание вариантов вычеркивания. Описание начинается с числа \(C\) \((0 \le C \lt N)\) — количества точек, в которых, по мнению Кварка, клада быть не может. Следующие \(C\) чисел задают номера этих точек.
Выведите \(Q\) строк. В каждой строке выведите одно целое число — длину минимального маршрута при соответствующем варианте вычеркивания точек.
3 0 45 10 45 0 30 10 30 0 2 0 1 3
40 45
5 0 14 20 17 14 14 0 15 19 18 20 15 0 15 16 17 19 15 0 14 14 18 16 14 0 2 3 5 4 3 0
14 58