Formato do arquivo de entrada

A entrada é um arquivo-texto padrão ASCII. Cada linha do texto é formada por uma seqüência de valores inteiros separados por um espaço. Os valores codificam a distância entre dois vértices $u$ e $v$, ou seja, o custo de cada aresta $(u, v)$.

Como a matriz de distâncias é simétrica e não é necessário representar a diagonal principal (pois todos os seus valores são 0), temos que o arquivo representa apenas o triângulo superior direito da matriz. Ou seja: Convencionando que os vértices são indexados de 1 a $\vert V\vert$, temos que a 1^a linha codifica os custos das arestas $(1, 2)$ a $(1, \vert V\vert)$, a segunda linha codifica os custos de $(2, 3)$ a $(2, \vert V\vert)$, e assim por diante, até a $[\vert V\vert-1]$-ésima linha, que codifica o custo da aresta $(\vert V\vert-1, \vert V\vert)$. Obviamente, pela simetria da matriz, a primeira linha do arquivo também codifica os custos das arestas $(2, 1)$ a $(\vert V\vert, 1)$, etc.

O programa determina a quantidade de vértices a partir do número de valores descritos na primeira linha de dados, a não ser que essa quantidade seja informada como parâmetro de linha de comando.

Para efeito de leitura do arquivo, apenas a primeira linha que começa com um caractere numérico é considerada para preencher a matriz de custos. Em outras palavras, é possível que os dados sejam precedidos por qualquer número de linhas de texto, que serão ignoradas. Isto permite que sejam usados como entrada os arquivos no formato .tsp, descritos e usados no projeto TSPLIB (http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/), que contêm uma série de linhas de cabeçalho que descrevem a instância do problema. Se for este o caso, é importante notar que todas essas informações são ignoradas: o programa espera que o formato de dados descreva o triângulo superior direito da matriz.

Um arquivo que representa uma instância com 7 vértices poderia ser o seguinte:

3 5 48 48 8 8
3 48 48 8 8
72 72 48 48
0 6 6
6 6
0

Um exemplo que inclui o cabeçalho no formato .tsp é visto a seguir:

NAME: paa7
TYPE: TSP
COMMENT: Instancia para PAA-2003, TP2
DIMENSION: 7
EDGE_WEIGHT_TYPE: EXPLICIT
EDGE_WEIGHT_FORMAT: UPPER_ROW
EDGE_WEIGHT_SECTION
3 5 48 48 8 8
3 48 48 8 8
72 72 48 48
0 6 6
6 6
0

Estes arquivos representam a instância do problema proposto na questão 2.f.