El "problema del viajante de comercio" plantea la siguiente cuestión: "Dada una lista de ciudades y las distancias entre cada par de ciudades, ¿cuál es la ruta más corta posible que visita cada ciudad y regresa a la ciudad de origen?" Es un problema NP-difícil en optimización combinatoria, importante en investigación de operacoines e informática teórica. (Citado de "https://en.wikipedia.org/wiki/Travelling_salesman_problem".)

En este problema, se espera que encuentres, de una lista dada de ciclos, el que se acerque más a la solución de un problema del viajante de comercio.

Especificación de Entrada:

Cada archivo de entrada contiene un caso de prueba. Para cada caso, la primera línea contiene 2 enteros positivos N (≥2), el número de ciudades, y M, el número de aristas en un grafo no dirigido. Luego siguen M líneas, cada una describe una arista en el formato Ciudad1 Ciudad2 Dist, donde las ciudades están numeradas del 1 al N y la distancia Dist es positiva y no excede 100. La siguiente línea proporciona un entero positivo K que es el número de rutas, seguido de K líneas de rutas, cada una en el formato:

n C​1​​ C​2​​ ... C​n​​

donde n es el número de ciudades en la lista, y C​i​​'s son las ciudades en una ruta.

Especificación de Salida:

Para cada ruta, imprima en una línea Ruta X: DistTotal (Descripción) donde X es el índice (comenzando desde 1) de esa ruta, DistTotal su distancia total (si esta distancia no existe, imprima NA en su lugar), y Descripción es una de las siguientes:

• Ciclo simple del viajante si es un ciclo simple que visita cada ciudad;
• Ciclo del viajante si es un ciclo que visita cada ciudad, pero no un ciclo simple;
• No es un ciclo del viajante si NO es un ciclo que visita cada ciudad.

Finalmente imprima en una línea Distancia más corta(X) = DistTotal donde X es el índice del ciclo que se acerca más a la solución de un problema del viajante de comercio, y DistTotal es su distancia total. Se garantiza que dicha solución es única.

Entrada de Muestra:

6 10
6 2 1
3 4 1
1 5 1
2 5 1
3 1 8
4 1 6
1 6 1
6 3 1
1 2 1
4 5 1
7
7 5 1 4 3 6 2 5
7 6 1 3 4 5 2 6
6 5 1 4 3 6 2
9 6 2 1 6 3 4 5 2 6
4 1 2 5 1
7 6 1 2 5 4 3 1
7 6 3 2 5 4 1 6

Salida de Muestra:

Ruta 1: 11 (Ciclo simple del viajante) Ruta 2: 13 (Ciclo simple del viajante) Ruta 3: 10 (No es un ciclo del viajante) Ruta 4: 8 (Ciclo del viajante) Ruta 5: 3 (No es un ciclo del viajante) Ruta 6: 13 (No es un ciclo del viajante) Ruta 7: NA (No es un ciclo del viajante) Distancia más corta(4) = 8

using namespace std;

const int MAX_CIUDADES = 500; const int INFINITO = INT_MAX;

int matrizDistancias[MAX_CIUDADES][MAX_CIUDADES]; int numCiudades, numAristas;

void inicializarGrafo() { for (int i = 1; i <= numCiudades; i++) { for (int j = 1; j <= numCiudades; j++) { matrizDistancias[i][j] = INFINITO; } } }

void procesarEntrada() { cin >> numCiudades >> numAristas; inicializarGrafo();

for (int i = 0; i < numAristas; i++) {
    int ciudad1, ciudad2, distancia;
    cin >> ciudad1 >> ciudad2 >> distancia;
    matrizDistancias[ciudad1][ciudad2] = distancia;
    matrizDistancias[ciudad2][ciudad1] = distancia;
}

}

bool esCicloSimple(const vector& ruta) { if (ruta.front() != ruta.back() || ruta.size() != numCiudades + 1) { return false; }

vector<bool> visitada(numCiudades + 1, false);
for (size_t i = 0; i < ruta.size() - 1; i++) {
    if (visitada[ruta[i]]) {
        return false;
    }
    visitada[ruta[i]] = true;
}

return true;

}

bool esCicloCompleto(const vector& ruta) { if (ruta.front() != ruta.back() || ruta.size() < numCiudades + 1) { return false; }

vector<bool> visitada(numCiudades + 1, false);
for (size_t i = 0; i < ruta.size() - 1; i++) {
    visitada[ruta[i]] = true;
}

for (int i = 1; i <= numCiudades; i++) {
    if (!visitada[i]) {
        return false;
    }
}

return true;

}

int calcularDistancia(const vector& ruta) { int distanciaTotal = 0; for (size_t i = 1; i < ruta.size(); i++) { if (matrizDistancias[ruta[i-1]][ruta[i]] == INFINITO) { return -1; } distanciaTotal += matrizDistancias[ruta[i-1]][ruta[i]]; } return distanciaTotal; }

void procesarRutas(int numRutas) { int mejorDistancia = INFINITO; int mejorIndice = -1;

for (int i = 0; i < numRutas; i++) {
    int numCiudadesRuta;
    cin >> numCiudadesRuta;
    
    vector<int> ruta(numCiudadesRuta);
    for (int j = 0; j < numCiudadesRuta; j++) {
        cin >> ruta[j];
    }
    
    int distancia = calcularDistancia(ruta);
    string descripcion;
    
    if (distancia == -1) {
        descripcion = "No es un ciclo del viajante";
        cout << "Ruta " << i+1 << ": NA (" << descripcion << ")" << endl;
    } else {
        if (esCicloSimple(ruta)) {
            descripcion = "Ciclo simple del viajante";
            cout << "Ruta " << i+1 << ": " << distancia << " (" << descripcion << ")" << endl;
            if (distancia < mejorDistancia) {
                mejorDistancia = distancia;
                mejorIndice = i+1;
            }
        } else if (esCicloCompleto(ruta)) {
            descripcion = "Ciclo del viajante";
            cout << "Ruta " << i+1 << ": " << distancia << " (" << descripcion << ")" << endl;
            if (distancia < mejorDistancia) {
                mejorDistancia = distancia;
                mejorIndice = i+1;
            }
        } else {
            descripcion = "No es un ciclo del viajante";
            cout << "Ruta " << i+1 << ": " << distancia << " (" << descripcion << ")" << endl;
        }
    }
}

cout << "Distancia más corta(" << mejorIndice << ") = " << mejorDistancia << endl;

}

int main() { procesarEntrada();

int numRutas;
cin >> numRutas;

procesarRutas(numRutas);

return 0;

}