#include <iostream>
#include <fstream>
#include <string>
#include <queue>
#include <sstream>
#define INF 100000
const int N=24;
using namespace std;



string to_string(int a){
    string tmp;
    stringstream ss;
    ss<<a;
    return ss.str();
}

int sortT(int** mas,queue<int>* path,int a,int b){
     queue<int> edges;
     int curr;
     edges.push(a);
     do{
        if(edges.empty()) return -1;
        curr=edges.front();
        edges.pop();
        path->push(curr);
        for(int i=0;i<N;i++) if(mas[curr][i]>0) edges.push(i);
     } while(curr!=b);
        path->push(curr);
     return 0;
}

int dyn(int** mas,int a,int b){
    int dist[N];
    queue<int> path;
    int prev[N];
    for(int i=0;i<N;i++) dist[i]=INF;
    dist[a]=0;
    switch(sortT(mas,&path,a,b)){
        case -1:{
            cout<<"ureachable";
            return -1;
            break;
        }
        case -2:{
            cout<<"cycle";
            return -1;
            break;
        }
    }
    int i;
    for(int i;path.empty()==false;path.pop()){
        i=path.front();
        for(int j=0;j<N;j++){
            if(j==i || mas[i][j]<1) continue;
            if(dist[j]>dist[i]+mas[i][j]){
                dist[j]=dist[i]+mas[i][j];
                prev[j]=i;
            }
        }
    }
    cout<<"Shortest path value is "<<dist[b]<<endl;
    cout<<"Path:";
    string ResPath="->"+to_string(b);
    for(int i=b;i!=a;i=prev[i]) ResPath="->"+to_string(prev[i])+ResPath;
    ResPath.erase(ResPath.begin(),ResPath.begin()+1);
    cout<<ResPath<<endl;
    return 0;
}

void printGraph(int **mas){
    cout<<"   ";
    for(int i=0;i<N;i++) {
        if(i<10) cout<<' ';
        cout<<' '<<i;
    }
    cout<<endl<<"  ";
    for(int i=0;i<N;i++) cout<<"___";
    cout<<endl;
    for(int i=0;i<N;i++){
        if(i<10) cout<<' ';
        cout<<i<<"| "<<mas[i][0];
        for(int j=1;j<N;j++) {
            if(mas[i][j]>9) cout<<' '; else cout<<"  ";
            cout<<mas[i][j];
        }
        cout<<endl;
    }
}

void clearGraph(int **mas){
    for(int i=0;i<N;i++) delete [] mas[i];
    delete [] mas;
}

int main() {
    int** graph=new int*[N];
    for(int i=0;i<N;i++) graph[i]=new int[N];
    ifstream file("test.txt");
    for(int i=0;i<N;i++)
    for(int j=0;j<N;j++) file>>graph[i][j];
    file.close();

    int start,end;
    cout<<"Write start edge:";
    cin>>start;
    cout<<"Write end edge:";
    cin>>end;
    printGraph(graph);
    getchar();
    dyn(graph,start,end);
    clearGraph(graph);
    return 0;
}