Baraj I
Problema 2

Patrule

Pentru a asigura linistea pe toata durata desfasurarii Olimpiadei Nationale in orasul Oradea, Inspectoratul Local de Politie a hotarat sa instituie patrule care sa asigure protectia tuturor obiectivelor din oras. Fiecare patrula, avand la dispozitie o masina, urmeaza sa "acopere" doua sau mai multe obiective, intre care politistii patrulei se vor deplasa continuu, formand un circuit. Pentru a nu alarma cetatenii, prin fiecare obiectiv va trece doar o patrula si doar o singura data pe parcursul fiecarui circuit. Inspectoratul dispune de suficiente masini si oameni, principala problema fiind carburantul. De aceea sunteti rugati ca, fiind date distantele dintre obiectivele din oras, sa ajutati Inspectoratul sa gaseasca un mod de organizare a patrulelor astfel incat suma totala a distantelor parcurse de acestea sa fie minima. Prin distanta de la un obiectiv la altul se intelege lungimea (pozitiva) a traseului ce trebuie parcurs de patrula pentru a se deplasa de la primul obiectiv la al doilea; se presupune ca un astfel de traseu nu trece prin nici un alt obiectiv.
Precizari:

- Nu este obligatoriu sa existe un traseu direct (care sa nu treaca prin nici un alt obiectiv) intre oricare doua obiective. Pentru doua obiective care nu sunt legate printr-un traseu direct, distanta dintre ele este data ca 0.
- Īn oras pot exista strazi cu sens unic, deci nu este obligatoriu ca distanta intre doua obiective sa fie aceeasi in ambele sensuri; mai mult, este posibil ca numai intr-un sens sa existe traseu direct.
- Desi in mod normal reteaua de strazi a orasului asigura existenta unui drum (direct sau indirect) intre oricare doua obiective, in orice sens, datorita lucrarilor de intretinere si extindere in desfasurare, este posibil sa existe obiective intre care nu se poate ajunge (direct sau trecand prin alte obiective).
- Este obligatoriu ca in solutie sa fie "acoperite" toate obiectivele din oras.
- Este posibil si sa nu existe nici o solutie.
- Īn caz ca exista mai multe solutii optime, se cere una singura.

Intrare:
Īn fisierul de intrare PATRULE.IN se gaseste un singur set de date, structurat astfel:
N - numarul de obiective din oras (1 <= N <= 50)
d₁₁ d₁₂ ... d_1N - distantele (orientate) intre oricare doua obiective
d₂₁ d₂₂ ... d_2N - separate printr-un spatiu. Distantele sunt intregi din
.................... intervalul [ 0, 500],o distanta egala cu 0 insemnand
d_N1 d_N2 ... d_NN ca nu exista drum direct intre obiectivele respective

Iesire:

Fisierul de iesire PATRULE.OUT va contine pe prima linie costul minim al unei organizari a patrulelor, iar restul liniilor vor contine descrierea uneia dintre organizarile optime, astfel: a doua linie va contine numarul de patrule, iar fiecare dintre restul de linii va descrie o patrula, prin obiectivele (in ordinea in care apar ele in circuit) parcurse de aceasta. Īn cazul in care nu exista solutie, fisierul de iesire va contine doar un 0.

Exemplu:

PATRULE.IN:
5
0 2 0 1 3
4 0 1 0 1
2 1 0 3 6
3 0 0 0 0
2 1 1 4 0
PATRULE.OUT:
7
2
1 4
2 5 3

Timp de executie: maxim 5 secunde/test.
Punctaj maxim: 50 puncte.