Решение задачи китайского почтальона

#include <iostream>
#include <list>
#include <vector>
#include <locale>
#include <algorithm>
#include <cstdio>
#define CHARS 26
#define inf 1000000000
using namespace std;
 
class Graph
{
    int V;
    list<int> *adj;
    int *in;
public:
    Graph(int V);
    ~Graph()   { delete[] adj; delete[] in; }
    void addEdge(int v, int w) { adj[v].push_back(w);  (in[w])++; }
    bool isEulerianCycle();
    bool isSC();
    void DFSUtil(int v, vector<bool> &visited);
    void getTranspose(Graph &g);
    Graph(const Graph &a){
        V = a.V;
        adj = new list<int>[V];
        in = new int[V];
        for (int v = 0; v < V; v++){
            for (list<int>::iterator it = a.adj[v].begin(); it != a.adj[v].end(); it++)
                adj[v].push_back(*it);
        }
 
        for (int i = 0; i < V; i++)
            in[i] = a.in[i];
    }
};
Graph::Graph(int V)
{
    this->V = V;
    adj = new list<int>[V];
    in = new int[V];
    for (int i = 0; i < V; i++)
        in[i] = 0;
}
bool Graph::isEulerianCycle()
{
    if (isSC() == false)
        return false;
    for (int i = 0; i < V; i++)
        if (adj[i].size() != in[i])
            return false;
    return true;
}
void Graph::DFSUtil(int v, vector<bool> &visited)
{
    visited[v] = true;
 
 
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            DFSUtil(*i, visited);
}
void Graph::getTranspose(Graph &g)
{
    for (int v = 0; v < V; v++)
    {
        list<int>::iterator i;
        for (i = adj[v].begin(); i != adj[v].end(); ++i)
        {
            g.adj[*i].push_back(v);
            (g.in[v])++;
        }
    }
}
bool Graph::isSC()
{
    vector<bool> visited(V, false);
    int n;
    for (n = 0; n < V; n++)
        if (adj[n].size() > 0)
            break;
    if (n >= V)
        return true;
    DFSUtil(n, visited);
    for (int i = 0; i < V; i++)
        if (adj[i].size() > 0 && visited[i] == false)
            return false;
    Graph gr(V);
    getTranspose(gr);
    for (int i = 0; i < V; i++)
        visited[i] = false;
    gr.DFSUtil(n, visited);
    for (int i = 0; i < V; i++)
        if (adj[i].size() > 0 && visited[i] == false)
            return false;
    return true;
}
int main()
{
    setlocale(LC_ALL, "RUSSIAN");
    int n, m;
    cout << "введите количество вершин и количество ребер: \n";
    cin >> n >> m;
    int graph[15][15], edgenum[15] = {};
    for (int i = 0; i < n; i++){
        for (int j = 0; j < n; j++){
            graph[i][j] = inf;
        }
    }
    Graph g(n);
    int weightsum = 0;
    cout << "введите начало, конец ребра и вес: \n";
    for (int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        g.addEdge(a, b);
        graph[a][b] = min(graph[a][b], c);
        graph[b][a] = min(graph[b][a], c);
        weightsum += c;
        edgenum[a]++;
        edgenum[b]++;
    }
    if (g.isEulerianCycle()){
        cout << "граф является эйлеровым \n";
        vector<int> oddnode;
        for (int i = 0; i < n; i++){
            if (edgenum[i] % 2 == 1) oddnode.push_back(i);
        }
        int oddnum = oddnode.size();
        for (int k = 0; k < n; k++){
            for (int i = 0; i < n; i++){
                for (int j = 0; j < n; j++){
                    graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);
                }
            }
        }
        int result[1 << 15] = {};
        for (int i = 0; i < oddnum; i++){
            result[(1 << i)] = -1;
        }
        for (int i = 0; i < (1 << oddnum); i++){
            if (result[i] == -1) continue;
            for (int j = 0; j < oddnum; j++){
                for (int k = j + 1; k < oddnum; k++){
                    if ((i & (1 << j)) != 0 || (i & ((1 << k))) != 0) continue;
                    int news = oddnode[j], newt = oddnode[k];
                    int tmp = (i | (1 << j) | (1 << k));
                    if (graph[news][newt] != inf && tmp != i){
                        if (result[tmp] == 0) result[tmp] = result[i] + graph[news][newt];
                        else result[tmp] = min(result[tmp], result[i] + graph[news][newt]);
                    }
                }
            }
        }
        cout << "кратчайший путь: ";
        cout << weightsum + result[(1 << oddnum) - 1] << endl;
    }
    else
        cout << "граф не является эйлеровым \n";
    system("pause");
    return 0;
}