Dijkstra

using System;
using System.Collections.Generic;
using System.IO;
using Priority_Queue;

//Problem 1 - „Misja”

//Jest XXXIII wiek.Ludzie podróżują ultra-szybkimi statkami kosmicznymi pomiędzy zawieszonymi
//w przestrzeni międzygwiezdnej ogromnymi hipermiastami.Kosmos jest w stanie wojny i dowolne
//podróżowanie w przestrzeni kosmicznej jest zabronione. Do komunikacji służą tylko specjalnie
//wybrane korytarze komunikacyjne łączące ze sobą hipermiasta. W tych korytarzach statki
//kosmiczne poruszają się z prędkością światła, jednak odległości między hipermiastami są duże –
//liczone zwykle w godzinach świetlnych.Stąd podróże trwają pewien czas.Niektóre hipermiasta są
//jednak połączone specjalnymi tunelami czasoprzestrzennymi i dzięki temu podróż między nimi nic
//nie trwa (!). Takich tuneli w całej przestrzeni jest jednak co najwyżej 50. Z racji tego, że trwa
//kosmiczna wojna, to działania szpiegowskie są zakrojone na dużą skalę.Pewien szpieg znajduje się
//w pierwszym hipermieście i ma za zadanie wykraść tajne informacje, które są ukryte w ostatnim z
//hipermiast.W związku z tym musi przemieścić się on z hipermiasta nr 1 do hipermiasta nr n.Po
//drodze może on swobodnie poruszać się zwykłymi korytarzami.Jednak podróżowanie tunelami
//czasoprzestrzennymi jest niebezpieczne ze względu na ich niestabilność – szpieg może po prostu
//zniknąć w wyższym wymiarze. Nie da się jednak ukryć, że tunele mogą pomóc w szybszym
//pokonywaniu trasy. Szpieg stosuje w związku z tym zasadę ograniczania ryzyka i w czasie całej
//podróży pozwala sobie na skorzystanie z co najwyżej k różnych tuneli czasoprzestrzennych (z
//każdego po razie). Misja jest krytyczna i od jej powodzenia mogą zależeć losy wszechświata.
//Szpieg musi ją wykonać w jak najkrótszym czasie.Czy pomożesz mu w wykonaniu zadania i
//znalezienia najkrótszej czasowo trasy?

//Wejście:
//W pierwszej linii wejścia podana jest liczba n hipermiast, m korytarzy oraz maksymalną liczbę k
//tuneli czasoprzestrzennych, których można użyć (1<n<=10000, 1<=m<=100000, 1<=k<=3). W
//kolejnych m liniach są podane informacje dotyczące korytarzy: po 3 liczby całkowite oznaczające
//odpowiednio numery połączonych miast oraz długość korytarza(co najwyżej 100 godzin
//świetlnych).

//Wyjście:
//W pierwszej linii wyjście należy podać czas optymalnej trasy, a w kolejnej linii po kolei ciąg liczb
//(numerów miast) opisujących trasę.

//Przykład:

//Wejście:
//5 7 1
//1 3 3 //między 1 i 3 korytarz powietrzny o długości 3 godzin świetl
//2 4 2 //itd.
//2 3 3
//1 2 0 //tunel czasoprzestrzenny
//3 4 0 //tunel czasoprzestrzenny
//3 5 3
//4 5 2

//Wyjście:
//4
//1 2 4 5

namespace Dijkstra
{
    class Trasa
    {
        public int koncowy;
        public int koszt;

        public Trasa(int koncowy, int koszt)
        {
            this.koncowy = koncowy;
            this.koszt = koszt;
        }
    }

    class Poprzednik
    {
        public int poprzednik;
        public bool zero;

        public Poprzednik(int poprzednik, bool zero)
        {
            this.poprzednik = poprzednik;
            this.zero = zero;
        }
    }

    public class WezelZZero
    {
        public int wierzcholek;
        public int ile_tuneli;

        public WezelZZero(int wierzcholek, int ile_tuneli)
        {
            this.wierzcholek = wierzcholek;
            this.ile_tuneli = ile_tuneli;
        }
    }

    class Program
    {
        public static int licznik = 0;

        static void Main()
        {
            int wierzcholkow = 0, korytarzy = 0, tuneli = 0;
            List<Trasa>[] lista = null;
            Wczytywanie(ref lista, ref wierzcholkow, ref korytarzy, ref tuneli);
            DateTime start = DateTime.Now;
            Rozwiazanie(wierzcholkow, lista, tuneli);
            DateTime koniec = DateTime.Now;
            Console.WriteLine($"Liczba operacji elemntarnych: {licznik}");
            Console.WriteLine($"Czas działnia programu: {(koniec - start).TotalMilliseconds} milisekund = {(koniec - start).TotalSeconds} sekund");
            Console.ReadKey();
        }

        static void Rozwiazanie(int wierzcholkow, List<Trasa>[] lista_incydencji, int tuneli)
        {
            int[,] d = new int[tuneli + 1, wierzcholkow]; //Tablica wag
            Poprzednik[,] p = new Poprzednik[tuneli + 1, wierzcholkow]; //Poprzednicy (poprzednik i czy wykorzystany tunel do dojścia)
            bool[,] odwiedzeni = new bool[tuneli + 1, wierzcholkow]; //Tablica odwiedzonych wierzchołków
            SimplePriorityQueue<WezelZZero, int> kolejka_priorytetowa = new SimplePriorityQueue<WezelZZero, int>(); //Kolejka priorytetowa
            for (int i = 0; i <= tuneli; i++) //Przypisanie zer i nieskończoności w tablicy wag
            {
                for (int j = 0; j < wierzcholkow; j++)
                {
                    if (j == 0) d[i, j] = 0;
                    else d[i, j] = int.MaxValue;
                }
            }
            kolejka_priorytetowa.Enqueue(new WezelZZero(0, 0), 0); //Wierzchołek początkowy 0 z 0 przejściami przez tunele o wadze 0
            while (kolejka_priorytetowa.Count != 0) //Dopóki jest jakiś wierzchołek w kolejce
            {
                var wierzcholek = kolejka_priorytetowa.Dequeue(); //Zdjęcie z kolejki elementu o najwyższym priorytecie (najmniejsza odległość)
                odwiedzeni[wierzcholek.ile_tuneli, wierzcholek.wierzcholek] = true; //Wierzchołek w którym jesteśmy zaznaczamy jako odwiedzony (ile tuneli/wierzchołek)
                if (wierzcholek.wierzcholek == wierzcholkow - 1) break; //Jeżeli jesteśmy w ostatnim wierzchołku to nic się nie zmieni więc nie idziemy dalej
                foreach (Trasa docelowy_wierzcholek in lista_incydencji[wierzcholek.wierzcholek]) //Dla danego wierzchołka sprawdzamy każdego jego sąsiada
                {
                    licznik++;
                    if (odwiedzeni[wierzcholek.ile_tuneli, docelowy_wierzcholek.koncowy] == false) //Jeżeli wierzchołek, do którego chcemy iść nie został jeszcze odwiedzony
                    {

                        if (docelowy_wierzcholek.koszt == 0 && wierzcholek.ile_tuneli != tuneli) //Jeżeli koszt to 0 i liczba tuneli nie przekracza max tuneli
                        {
                            if (d[wierzcholek.ile_tuneli, wierzcholek.wierzcholek] < d[wierzcholek.ile_tuneli + 1, docelowy_wierzcholek.koncowy]) //Jeżeli trasa z nie przejściem przez tunel jest gorsza od trasy z przejściem przez tunel to jej nie bierzemy, nie wykroczy poza tablice bo tuneli != tuneli
                            {
                                d[wierzcholek.ile_tuneli + 1, docelowy_wierzcholek.koncowy] = d[wierzcholek.ile_tuneli, wierzcholek.wierzcholek]; //Sprawdza, czy nie ma już innej lepszej trasy wykorzystującej tunel, jeżeli nie to wchodzimy, jeżeli jest inna, wykorzystująca tunel i jest lepsza to nie zmieniamy
                                p[wierzcholek.ile_tuneli + 1, docelowy_wierzcholek.koncowy] = new Poprzednik(wierzcholek.wierzcholek, true); //poprzednik TRUE - wykorzystuje tunel
                                var temp = new WezelZZero(docelowy_wierzcholek.koncowy, wierzcholek.ile_tuneli + 1); //Wstawienie na kolejke kolejnego elementu
                                if (kolejka_priorytetowa.Contains(temp)) kolejka_priorytetowa.UpdatePriority(temp, d[wierzcholek.ile_tuneli + 1, docelowy_wierzcholek.koncowy]); //Aktualizacja wag w kolejce
                                else kolejka_priorytetowa.Enqueue(temp, d[wierzcholek.ile_tuneli + 1, docelowy_wierzcholek.koncowy]); //Dodanie do kolejki
                            }
                        }
                        else if (d[wierzcholek.ile_tuneli, wierzcholek.wierzcholek] + docelowy_wierzcholek.koszt < d[wierzcholek.ile_tuneli, docelowy_wierzcholek.koncowy] && docelowy_wierzcholek.koszt != 0) //Klasyczna Dijkstra - jeżeli droga z obecnego do końcowego plus koszt jest mniejsza od wagi końcowego to lecimy
                        {
                            d[wierzcholek.ile_tuneli, docelowy_wierzcholek.koncowy] = d[wierzcholek.ile_tuneli, wierzcholek.wierzcholek] + docelowy_wierzcholek.koszt;
                            p[wierzcholek.ile_tuneli, docelowy_wierzcholek.koncowy] = new Poprzednik(wierzcholek.wierzcholek, false);
                            var temp = new WezelZZero(docelowy_wierzcholek.koncowy, wierzcholek.ile_tuneli);
                            if (kolejka_priorytetowa.Contains(temp)) kolejka_priorytetowa.UpdatePriority(temp, d[wierzcholek.ile_tuneli, docelowy_wierzcholek.koncowy]);
                            else kolejka_priorytetowa.Enqueue(temp, d[wierzcholek.ile_tuneli, docelowy_wierzcholek.koncowy]);
                        }

                    }
                }
            }
            Wypisywanie(d, p, wierzcholkow, tuneli);
        }

        static void Wypisywanie(int[,] d, Poprzednik[,] p, int wierzcholkow, int tuneli)
        {
            int min = int.MaxValue;
            int wiersz = 0;
            for (int i = 0; i <= tuneli; i++) //Znalezienie wiersza z najmniejszą wartością w ostatniej kolumnie (ostatni wierzchołek)
            {
                if (d[i, wierzcholkow - 1] < min)
                {
                    min = d[i, wierzcholkow - 1];
                    wiersz = i;
                }
            }

            if (min == int.MaxValue) //Nie udało się dojść do ostatniego wierzchołka
            {
                using (StreamWriter stw = new StreamWriter("out.txt"))
                {
                    stw.WriteLine(min);
                    Console.WriteLine(min);
                    Console.WriteLine("");
                    stw.WriteLine("");
                }
                return;
            }

            Poprzednik temp = p[wiersz, wierzcholkow - 1]; //Poprzednik pobierany z tablicy
            string wynik = wierzcholkow.ToString(); //Dodaje ostatni wierzchołek (5)

            while (temp != null) //Dopóki nie dojdziemy do końca poprzedników (0)
            {
                wynik = (temp.poprzednik + 1).ToString() + " " + wynik; //Dodanie poprzednika+1 bo liczymy od 0
                if (temp.zero == true) wiersz--; //Jeżeli wystąpił tunel, to zmniejszamy wiersz o 1
                temp = p[wiersz, temp.poprzednik]; //Aktualizacja poprzednika
            }

            using (StreamWriter stw = new StreamWriter("out.txt"))
            {
                stw.WriteLine(min);
                Console.WriteLine(min);
                Console.WriteLine(wynik);
                stw.WriteLine(wynik);
            }
        }
        static void Wczytywanie(ref List<Trasa>[] lista, ref int wierzcholkow, ref int korytarzy, ref int tuneli)
        {
            bool pierwsza_linia = true;
            string line;
            string[] tab = null;
            int x = 0, y = 0, z = 0;
            try
            {
                using (StreamReader str = new StreamReader("in0.txt"))
                {
                    while ((line = str.ReadLine()) != null)
                    {
                        tab = line.Split(' ');
                        if (pierwsza_linia == true)
                        {
                            pierwsza_linia = false;
                            wierzcholkow = Convert.ToInt32(tab[0]); //liczba wierzchołków
                            korytarzy = Convert.ToInt32(tab[1]); //liczba korytarzy (połączeń)
                            tuneli = Convert.ToInt32(tab[2]);
                            lista = new List<Trasa>[wierzcholkow];
                            for (int i = 0; i < wierzcholkow; i++)
                            {
                                lista[i] = new List<Trasa>();
                            }
                        }
                        else
                        {
                            x = Convert.ToInt32(tab[0]); //1 miasto
                            y = Convert.ToInt32(tab[1]); //2 miasto
                            z = Convert.ToInt32(tab[2]); //koszt połączenia
                            lista[x - 1].Add(new Trasa(y - 1, z));
                            lista[y - 1].Add(new Trasa(x - 1, z));
                        }
                    }
                }
            }
            catch (IOException)
            {
                Console.WriteLine("File not found...");
                Console.ReadKey();
                System.Diagnostics.Process.GetCurrentProcess().Kill();
                //Environment.Exit(0);
            }
        }
    }
}