namespace ConsoleApp2 // Note: actual namespace depends on the project name.
{
    internal class Program
    {
        static void Main(string[] args)
        {
            while (true)
            {
                Console.WriteLine("Для начала работы введиите 1");
                Console.WriteLine("Для завершения работы введиите 2");
                Console.WriteLine("Для начала работы с ручным вводом значений введиите 3");
                int f = Convert.ToInt32(Console.ReadLine());
                bool v = false;
                switch (f)
                {
                    case 1:
                        double[,] vs = {
                //{0,15,26,52,29,24},
                //{13,0,28,28,19,15},
                //{24,13,0,14,19,30},
                //{46,55,35,0,20,65},
                //{23,15,15,28,0,40},
                //{35,16,14,10,12,0 }

                {0,1,2,3,5},
                {1,0,4,4,3},
                {2,4,0,1,2},
                {7,4,1,0,3},
                {5,3,2,3,0}

                // {0,15,12,24,19},
                //{6,0,25,30,50},
                //{25,15,0,12,15},
                //{20,10,10,0,15},
                //{15,20,10,11,0}
                };
                        int g = 5;
                        resh(vs, g);
                        break;

                    case 2:
                        v = true;
                        break;
                    case 3:
                        Console.WriteLine("Введите размерность:");
                        int g1 = 3;
                        g1 = Convert.ToInt32(Console.ReadLine());
                        double[,] vs1 = new double[g1, g1];
                        for (int i = 0; i < g1; i++)
                        {
                            for (int j = 0; j < g1; j++)
                            {
                                vs1[i, j] = Convert.ToDouble(Console.ReadLine());
                            }
                        }
                        resh(vs1, g1);
                        break;


                }

                if (v)
                {
                    break;
                }
            }

        }
        public static void resh(double[,] vs, int g)
        {
            List<List<int>> f1 = new List<List<int>>();
            List<double> t = new List<double>();

            for (int n = 0; g != n; n++)
            {
                List<List<int>> f = new List<List<int>>();
                List<int> list = new List<int>();
                f.Clear();
                f.Add(list);
                list.Add(n);

                while (f[0].Count <= g)
                {

                    List<List<int>> z = new List<List<int>>();


                    for (int k = 0; k < f.Count; k++)
                    {
                        List<int> listic = new List<int>();
                        for (int i = 0; i < g; i++)
                        {
                            listic.Add(i);
                        }
                        for (int i = f[k].Count - 1; i >= 0; i--)
                        {
                            listic.Remove(f[k][i]);


                        }
                        double max = double.MaxValue;
                        List<int> vs1 = new List<int>();


                        for (int i = 0; i < listic.Count; i++)
                        {
                            if (f[k].Last() == listic[i])
                            {
                                continue;
                            }
                            double kl = vs[f[k].Last(), listic[i]];
                            if (max >= kl)
                            {
                                max = kl;
                                vs1.Add(listic[i]);
                            }

                        }
                        z.Add(new List<int>(vs1.ToArray()));
                    }
                    bool ret = true;
                    int x = f.Count;
                    for (int k = 0; k < x; k++)
                    {
                        if (f[k].Count == g)
                        {
                            f[k].Add(f[k].First());
                            continue;
                        }
                        for (int i = 0; i < z[k].Count - 1; i++)
                        {
                            if (z[k].Count == 0)
                            {
                                continue;
                            }
                            if (vs[f[k].Last(), z[k][i]] == vs[f[k].Last(), z[k].Last()])
                            {
                                f.Add(new List<int>(f[k].ToArray()));
                                f[f.Count - 1].Add(z[k][i]);
                            }
                        }
                        f[k].Add(z[k].Last());

                    }



                }

                for (int i = 0; i < f.Count; i++)
                {
                    double fun = 0;
                    for (int h = 0; h < f[i].Count - 1; h++)
                    {


                        fun += vs[f[i][h], f[i][h + 1]];


                    }
                    t.Add(fun);
                }
                for (int i = 0; i < f.Count; i++)
                {
                    f1.Add(f[i]);
                }

            }
            for (int i = 0; i < f1.Count; i++)
            {
                for (int j = 0; j < f1[i].Count; j++)
                {
                    Console.Write(f1[i][j] + 1);
                }
                Console.WriteLine("  Длинна маршрута = " + t[i]);
            }
            List<int> fi = new List<int>();
            for (int i = 0; i < f1.Count - 1; i++)
            {
                if (t[i] == t.Min())
                {
                    fi.Add(i);
                }
            }
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine("Самый короткий маршрут");
            for (int i = 0; i < fi.Count; i++)
            {
                for (int j = 0; j < f1[i].Count; j++)
                {
                    Console.Write(f1[fi[i]][j] + 1);
                }
                Console.WriteLine("  Длинна маршрута = " + t[fi[i]]);
            }
        }
    }
}