{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n #problem-body \u003e pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv id\u003d\"problem-body\"\u003e\n\t\u003cp\u003eAda the Ladybug é uma fazendeira bem conhecida. Como ela tem experiência em construir cercas e criar animais, foi solicitado pelo líder do zoológico local - Lichsteiner Leech - para ajudá-los a projetar um cercado para os animais.\u003c/p\u003e\n\t\u003cp\u003eO problema é o seguinte: O zoológico cria bestas muito raras chamadas Tyg3Rs. Existem poucos deles em um cercado quadrado \u003cstrong\u003eN x N\u003c/strong\u003e com quadrados de alturas diferentes. Os Tyg3Rs vivem em quadrados pequenos e os criadores querem que eles brinquem entre si. Inicialmente, não é possível viajar entre quadrados distintos, mas é possível conectar quaisquer dois quadrados adjacentes pelo custo da diferença absoluta de suas alturas (fazendo uma inclinação).\u003c/p\u003e\n\t\u003cp\u003eAgora, para cada subconjunto de Tyg3Rs, o zoológico quer saber o preço mínimo para conectar os quadrados de tal forma que cada Tyg3R possa chegar a todos os outros. Como a saída seria muito grande, eles querem apenas que você some esses custos.\u003c/p\u003e\n\t\u003cp\u003eComo sua boa amiga (e como as instâncias são muito grandes para ela lidar), ela pediu para você ajudá-la com este problema.\u003c/p\u003e\n\t\u003ch3\u003eEntrada\u003c/h3\u003e\n\t\u003cp\u003eA primeira linha contém \u003cstrong\u003eT\u003c/strong\u003e, o número de casos de teste.\u003c/p\u003e\n\t\u003cp\u003eA primeira linha de cada caso de teste contém \u003cstrong\u003e2 ≤ N ≤ 17\u003c/strong\u003e, o tamanho do quadrado grande.\u003c/p\u003e\n\t\u003cp\u003eCada uma das próximas \u003cstrong\u003eN\u003c/strong\u003e linhas contém \u003cstrong\u003eN\u003c/strong\u003e inteiros, as alturas de cada quadrado. Cada número está entre \u003cstrong\u003e0\u003c/strong\u003e e \u003cstrong\u003e1000\u003c/strong\u003e.\u003c/p\u003e\n\t\u003cp\u003eA próxima linha contém \u003cstrong\u003e 1 ≤ Q ≤ 10\u003c/strong\u003e, o número de Tyg3Rs.\u003c/p\u003e\n\t\u003cp\u003eAs próximas \u003cstrong\u003eQ\u003c/strong\u003e linhas contêm dois inteiros: \u003cstrong\u003e0 ≤ x, y \u0026lt; N\u003c/strong\u003e, as coordenadas dos Tyg3Rs. Observe que vários Tyg3Rs podem já viver no mesmo quadrado.\u003c/p\u003e\n\t\u003ch3\u003eSaída\u003c/h3\u003e\n\t\u003cp\u003ePara cada caso de teste, imprima a soma dos custos do caminho mais barato para conectar todos os subconjuntos de Tyg3Rs.\u003c/p\u003e\n\t\u003ch3\u003eExemplo\u003c/h3\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\r\n3\r\n1 2 1\r\n2 1 2\r\n1 2 1\r\n3\r\n0 0\r\n0 2\r\n2 1\r\n3\r\n5 5 5\r\n7 5 5\r\n3 4 4\r\n4\r\n0 0\r\n0 0\r\n0 0\r\n2 0\r\n3\r\n1 2 3\r\n4 5 6\r\n7 8 9\r\n2\r\n0 0\r\n2 2\r\n8\r\n1 8 5 2 3 6 7 4\r\n1 5 7 5 4 6 8 7\r\n9 8 7 4 5 2 3 6\r\n1 4 5 7 2 5 3 6\r\n5 2 1 2 4 5 8 5\r\n9 9 9 9 6 6 4 5\r\n2 2 3 4 9 1 9 1\r\n1 4 1 4 7 5 2 1\r\n5\r\n0 0\r\n5 6\r\n3 3\r\n2 1\r\n7 7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e12\r\n14\r\n8\r\n441\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\t\u003ch3\u003eExplicação da Entrada\u003c/h3\u003e\n\t\u003cp\u003ePreços dos subconjuntos do primeiro caso de teste\u003c/p\u003e\n\t\u003cpre\u003e000: 0\r\n100: 0\r\n010: 0\r\n001: 0\r\n110: 2\r\n101: 3\r\n011: 3\r\n111: 4\r\n\u003c/pre\u003e\n\t\u003cp\u003ePara o segundo caso de teste, cada subconjunto custa 0, a menos aqueles que consistem no último Tyg3R (e alguns outros) - esses custam 2.\u003c/p\u003e\n\t\u003cp\u003eO terceiro caso de teste tem apenas um subconjunto valioso (de ambos Tyg3Rs), que vai para a borda superior/direita e custa 8.\u003c/p\u003e\n\u003c/div\u003e"}}]}