#include <conio.h>
#include <iostream>
#include <string>
using namespace std;


struct station {  
    station* commonst;
    string namest;
    int way;
};


struct list {
    station* st;
    list* next;
};


station** getname(station*** mainst, int num,int index) {  // Функція поверне адресу вказівника ан станцію з потрібним нам ім ям.
    if (index == 1) {
        cout << "Введіть назву станції із якої Ви хочете почати обхід ліній метро в ширину: ";
    }
    else {
        if (index == 2) {
            cout << "Введіть назву станції із якої Ви хочете почати обхід ліній метро в глибину: ";
        }
    }
    string name;
    cin >> name;
    station** mst = *mainst;
    for (int i = 0; i < num; i++) {
        if (mst[i]->namest == name) {
            return &mst[i];
        }
    }
}


station** search(station*** mainst, int num, station* nm) { // Подібна до попередньої, але не потрібно вводити назву.
    station** mst = *mainst;
    for (int i = 0; i < num; i++) {
        if (mst[i]->namest == nm->namest) {
            return &mst[i];
        }
    }
}

station** searchind(station*** mainst, int num, int ind) { // Ця функція потрібна мені для пошуку мінімального шляху між станціями. Також поверне адресу вказівника але з потрібним мені індексом а не ім ям.
    station** mst = *mainst;
    for (int i = 0; i < num; i++) {
        if (i == ind) {
            return &mst[i];
        }
    }
}

bool add(station* qst, list* main) { // Ця функція потрібна для перевірки в стеку, списку, чи є даний елемент у ньому. (Якщо не має - поверне істину). 
    bool ret = true;
    if (main == nullptr) {
        return true;
    }
    else {


        if (main->next == nullptr) {
            if (qst->namest == main->st->namest) {
                return false;
            }
            else {
                return true;
            }
        }
        else {
            while (main!= nullptr) {
                if (qst->namest == main->st->namest) {
                    return false;
                }
                else {
                    main = main->next;
                    ret = true;
                }
            }
            if (ret == true) {
                return true;
            }
        }
    }
}


void mlist(list** main,station*stt) { // Функція для створення списку.
    if ((*main) == nullptr) {
        (*main) = new list;
        (*main)->st = (stt);
        (*main)->next = nullptr;
    }
    else {
        list* last = (*main);
        while (last->next!= nullptr) {
            last = last->next;
        }
        last->next = new list;
        last = last->next;
        last->st = (stt);
        last->next = nullptr;
    }
}


void qlist(list** queue, station* stt) { // Функції для створення стеку.
    if ((*queue) == nullptr) {
        (*queue) = new list;
        (*queue)->st = (stt);
        (*queue)->next = nullptr;
    }
    else {
        list* last = (*queue);
        while (last->next != nullptr) {
            last = last->next;
        }
        last->next = new list;
        last = last->next;
        last->st = (stt);
        last->next = nullptr;
    }
} 
void slist(list** stack, station* stt) {
    if ((*stack) == nullptr) {
        (*stack) = new list;
        (*stack)->st = (stt);
        (*stack)->next = nullptr;
    }
    else {
        list* stacklist = new list;
        stacklist->st = stt;
        stacklist->next = (*stack);
        (*stack) = stacklist;
    
    }
}


void width(list** queue, list** main, station*** mainst, int num) { // Функція для проходження графу в ширину .
    station* sst = *getname(mainst, num,1);
    
        (*queue) = new list;
        (*queue)->st = sst;
        (*queue)->next = nullptr;
        while ((*queue)) {
            station* addd = *search(mainst, num, (*queue)->st); // Доступ до вказівника з спільними вершинами.
            bool addmlist = add(addd, (*main)); 
            if (addmlist == true) { // Перевіряємо чи є елемент у списку
                mlist(main, addd);
                addd = addd->commonst;
            }
            
            while (addd != nullptr) {
                
                bool addqlist = add(addd, (*main));
                
                if (addqlist == true) {// Перевіряємо чи є елемент у стеку.
                    qlist(queue, addd);
                }
                addd = addd->commonst;
            }
            (*queue) = (*queue)->next;
        }
    
}


void depth(list** stack, list** main, station*** mainst, int num) { // Ця фунцыя працює практично як попередня.
    station* sst = *getname(mainst, num, 2);
    (*stack) = new list;
    (*stack)->st = sst;
    (*stack)->next = nullptr; {
        while ((*stack)) {
        station* addd = *search(mainst, num, (*stack)->st);
            bool addmlist = add(addd, (*main));
            if (addmlist == true) {
                mlist(main, addd);
                addd = addd->commonst;
                (*stack) = (*stack)->next;
            }

            while (addd) {

                bool addqlist = add(addd, (*main));

                if (addqlist == true) {
                    slist((stack), addd);
                }
                addd = addd->commonst;
            }
            
        }
    }
    
}


void printlist(list* main) { // Вивід всіх елементів списку.
    list* plist = main;
    cout << "||";
    while (plist) {
        cout << "->";
        cout << plist->st->namest;
        plist = plist->next;
    }
    cout << "||";
    
}


void print(station** mainst, int num) {  // Вивід всіх естінцій (без доступу до суміжніх їм).
    for (int i = 0; i < num; i++) {
        cout << "Назва " << i + 1 << "-ої станції метро: " << mainst[i]->namest << endl;
    }
}


void cincommonst(station*** mainst, int num) { // Ввід суміжніх вершин для кожної станції.
    for (int i = 0; i < num; i++) {
        cout << "Введіть к-сть суміжніх пересадок для станції " << (*mainst)[i]->namest << ": ";
        int numm;
        cin >> numm;
        station* newst = (*mainst)[i];
        for (int q = 0; q < numm; q++) {
            cout << "Введіть назву " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
            if (newst->commonst == nullptr) {
                (newst)->commonst = new station;
                (newst) = (newst)->commonst;
                cin >> (newst)->namest;
                cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
                cin >> (newst)->way;
                newst->commonst = nullptr;
            }
            else {
                while (newst->commonst) {
                    newst = newst->commonst;
                }
                (newst)->commonst = new station;
                (newst) = (newst)->commonst;
                cin >> (newst)->namest;
                cout << "Введіть довжину  " << q + 1 << "-ої пересадки із станції: " << (*mainst)[i]->namest << ": ";
                cin >> (newst)->way;
                newst->commonst = nullptr;
            }
        }
        cout << endl;
    }
}


void printcommonst(station** mainst, int num) { // Вивід усіх вершин.

    for (int i = 0; i < num; i++) {
        station* printst = mainst[i];
        while (printst->commonst) {
            printst = printst->commonst;
            cout << "Із станції " << mainst[i]->namest << " можна патрапити у станцію " << printst->namest << " із довжиною шляху: " << printst->way << " км." << endl;

        }
        cout << endl;
    }
}

int find(station*** sst, int num, string nm) { // Ця функція потрыбна мені для повернення індексу потрібної мені станції (використовую в пошуку мін. шляху).
    station** st = (*sst);
    int index = 0;
    for (int i = 0; i < num; i++) {
        if (st[i]->namest == nm) {
            index = i;
        }
        
    }
    return index;
}



void waymatrix(station*** main, int num) { // Можливо можна і простіше якось написати...
    int** matrix = nullptr;
    matrix = new int* [num];
    for (int i = 0; i < num; i++) { // Створюю матрицю та заповнюю її значеннями 99.
        matrix[i] = new int[num];
    }

    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            matrix[i][j] = 99;
        }
    }
    string name; 
    cout << "Введіть назву станції із якої Ви хочете найти мінімальні шляхи до пересадок: ";
    cin >> name;
    int index = find(main, num, name);
    for (int i = 0; i < num; i++) { // Обераю вершину до якої відстань 0 і позначаю її 66  ( весь стовпець)ахах... Я не знаю як мені описати цю функцію... Але вона працює.
        matrix[i][index] = 66;
    }
    int minindex = index;
    int sumway = 0;
    station* sst = nullptr;
    for (int i = 0; i < num; i++) {
        int minway = 100;
        sst = *searchind(main, num, minindex);
        
        
        while ((sst)) {
            index = find(main, num, (sst)->namest);
            
            if (matrix[i][index] != 66) {
                matrix[i][index] = sumway + (sst)->way;
                (sst) = (sst)->commonst;
            }
            else {
                (sst) = (sst)->commonst;
            }
        }

        for(int j = 0; j <num; j++){
            if (matrix[i][j] < minway) {
                minway = matrix[i][j];
                minindex = j;
                sumway = minway;
            }
            
        }
        cout << minindex << " " << sumway << endl;
        
        for (int a =i; a < num; a++) {
            if ((a+1) < num) {
                matrix[a+1][minindex] = 66;
            }
        }
    }
    for (int i = 0; i < num; i++) {
        for (int j = 0; j < num; j++) {
            cout << matrix[i][j] << " ";
        }
        cout << endl;
    }

}




int main(void) {
    setlocale(LC_ALL, "Ukr");
    station** mainst = nullptr;
    list* mainlist = nullptr;
    list* queue = nullptr;
    list* mainlist2 = nullptr;
    list* stack = nullptr;
    int num;
    cout << "Введіть к-сть станцій: ";
    cin >> num;
    mainst = new station * [num];
    for (int i = 0; i < num; i++) {
        cout << "Введіть назву " << i + 1 << "-ої станції метро: ";
        mainst[i] = new station;
        string name;
        cin >> name;
        mainst[i]->namest = name;
        mainst[i]->commonst = nullptr;
        mainst[i]->way = NULL;
    }
    print(mainst, num);

    cincommonst(&mainst, num);

    printcommonst(mainst, num);


    depth(&stack, &mainlist2, &mainst, num);

    printlist(mainlist2);

    cout << endl;
    
    width(&queue, &mainlist, &mainst, num);

    printlist(mainlist);
    
    cout << endl;

    waymatrix(&mainst, num);

    _getch();
    return 0;
}