[C]Find All Shortest Path

using namespace std;
int** map;
int node_count = 0;
int start_point = 0;
int end_point = 0;
int path_num = 0;
int min_path_weight = 0;
bool PathExist = true;
vector parent[100];
int* d;
bool* visit;
void build_map()
{
    //輸入地圖
    queue temp;
    int input = 0;
    while(scanf("%d",&input) == 1)//use queue to store the data
    {
        temp.push(input);
        node_count++;
    }
    node_count = (int)sqrt((float)node_count);//get the count
 
    map = new int* [node_count];//build the map
    for(int i = 0 ; i < node_count ; ++i)
    {
        map[i] = new int [node_count];
        for(int j = 0 ; j < node_count ; ++j)
        {
            if(temp.front() == 0)
            {
                map[i][j] = 0x3fffffff;//沒有連通設無限大
            }
            else
            {
                map[i][j] = temp.front();
            }
            temp.pop();
        }
    }
 
    //輸入起點終點
    char start_char;
    char end_char;
    scanf("%c",&start_char);
    start_point = start_char - 'A'; //change char to integer
    getchar();//ignore '\n' char
    scanf("%c",&end_char);
    end_point = end_char - 'A'; //change char to integer
 
    //for test
    //printf("%d %d\n",start_point,end_point);
    /*for(int i = 0 ; i < node_count ; ++i)
    {
        for(int j = 0 ; j < node_count ; ++j)
        {
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }*/
}
void Dijkstra(int s)
{
    d = new int[node_count];
    visit = new bool [node_count];
    for(int i = 0 ; i < node_count ; ++i) //初始化
    {
        d[i] = 1e9;
        parent[i].push_back(i);
        visit[i] = false;
    }
    d[s] = 0;
    parent[s][0] = s;
    for(int k = 0 ; k < node_count ; ++k)
    {
        int a = -1, b = -1 , min = 1e9;
        for(int i = 0 ; i < node_count ; ++i)//沒有走訪過的點中尋找一個最小值，第一次必定從起點開始
        {
            if(!visit[i] && d[i] < min)
            {
                a = i;
                min = d[i];
            }
        }
        if(a == -1)break;//起點連結的所有點都找完
 
        visit[a] = true;
        for(int b = 0 ; b < node_count ; ++b)//更新a點到所有沒走訪過點的路徑
        {
            if(!visit[b] && d[a] + map[a][b] <= d[b])
            {
                if(d[a] + map[a][b] < d[b])
                {
                    parent[b].clear();
                    d[b] = d[a] + map[a][b];
                }
                parent[b].push_back(a);
            }
        }
    }
}
void CheckIfPathExist(int e)
{
    //printf("%d\n",d[e]);
    if(d[e] == 1e9)
    {
        printf("沒有找到\n");
        PathExist = false;
    }
}
void CalcPathWeight(int s, int e) {//隨便找一條到的了的路徑計算
    if (e == s) {
        return ;
    }
    min_path_weight += map[ (parent[e][0]) ][e];
    CalcPathWeight( s, parent[e][0]);
}
void CalcPathNum(int s, int e) {//走訪所有路徑計算
    if (e == s) {
        path_num++;
        return ;
    }
    for (int i = 0 ; i < parent[e].size(); ++i ) {
        CalcPathNum( s, parent[e][i]);
    }
}
void searchPath(int s, int e, int sta[], int len) {
    /*
    *查找从源点v到终点u的路径，并输出
    *原理:一般的DisjointSet查找做變化，當某個點有兩個以上的Parent時，第二個Parent開始要將前一個的路徑補完整並且換行。
    *sta陣列用來記錄前面的路徑資訊，用來補足路徑資訊時會用到，len代表最小路徑樹的level值
    */
    if (e == s) {
        printf("%c",s+'A');
        return ;
    }
    sta[len] = e;
    for (int i = 0 ; i  0) {
            for (int j = len - 1  ; j >= 0 ; --j) {
                printf("->%c",sta[j]+'A');
            }
            cout << ("%c",e+'A');
    }
}
int main()
{
    freopen("DS4.txt","r",stdin);
    freopen("Ans4.txt","w",stdout);
    build_map();
    Dijkstra(start_point);
    CheckIfPathExist(end_point);
    if(PathExist)
    {
        CalcPathNum( start_point, end_point);
        printf("%d\n",path_num);
        CalcPathWeight( start_point, end_point);
        printf("%d\n",min_path_weight);
        int* sta = new int [node_count];//紀錄路徑資訊
        searchPath( start_point, end_point, sta, 0);
    }
}

using namespace std;
 
int **matrix;
int *min_d;//紀錄起點到各點的最短路徑
int **parent;//記錄在最短路徑時的父點是誰
int *visit;
int node = 0;//node數量
int pathnum = 0;//最小路徑總共有幾條
int minpathvalue = 0;//最小路徑的權值
int start_point = 0;
int end_point = 0;
int pathexist = 1; //判斷路徑是否存在
int *length;
 
void build_matrix()//算出DS4的資料個數並把值放進Queue中
{
    int temp;//資料個數
    int num=0;//資料值
    queue Q;
    while(1)
    {
        if(scanf("%d",&temp)!=1)break;
        num++;
        Q.push(temp);
    }
 
    //把起點跟終點讀進去
    char start,end;
    scanf("%c",&start);
    start_point = start-65;
    getchar();//把換行給消掉
    scanf("%c",&end);
    end_point = end-65;
 
    node = int(sqrt(float(num)));
    matrix = new int *[node];
    for(int i=0;i<node;i++)
    {
        matrix[i] = new int [node];
        for(int j=0;j<node;j++)
        {
            matrix[i][j] = Q.front(); 
            Q.pop();
            if(matrix[i][j] == 0) matrix[i][j] = 0x3fffffff;
        }
    }
    /*for(int i=0;i<node;i++)
    {
        for(int j=0;j<node;j++)
        {
            cout<<matrix[i][j];
        }
        cout<<endl;
    }
    cout<<start<<end;*/
}
 
void dijkstra(int startpoint)
{
    min_d = new int [node];
    parent = new int *[node];
    for(int i=0;i<node;i++){
        parent[i]= new int [node];
        for(int j=0;j<node;j++)
            {
                parent[i][j]=-1;
            }
        }
    visit = new int [node];
    for (int i=0; i<node; i++) visit[i] = 0;   // 初始化，每個點都還沒拜訪過
    for (int i=0; i<node; i++) min_d[i] = 1e9;
  
    min_d[start_point] = 0; //最小距離初始化(起點)
     
    for(int i = 0;i<node;i++)
    {
                parent[i][0]= i; //一開始父點的值都會是自己
    }
    //parent[start-65] = start-65;//父點初始化(起點)
  
    for (int i=0; i<node; i++)
    {
        int a = -1, b = -1, min = 1e9; //a跟b代表從某點到某點 一開始都沒跑所以設-1 距離設無限大
        for (int i=0; i<node; i++)
            if ( visit[i]!=1 && min_d[i] < min)
            {
                a = i;  // 記錄這一條邊
                min = min_d[i];
            }
  
        if (a == -1) break;     // 起點有連通的最短路徑都已找完
        visit[a] = 1;
  
        // 以新找到的最短路徑做更新
        for (b=0; b<node; b++){
            if (!visit[b] && min_d[a] + matrix[a][b] <= min_d[b])
            {
                if(min_d[a]+matrix[a][b] < min_d[b])
                {
                    parent[b][0] = a;
                    for(int i=1;i<node-1;i++)
                    {
                        parent[b][i]=-1;
                    }
                }
                else
                {
                    for(int j=1;j<node;j++)
                    {
                        if(parent[b][j]==-1)parent[b][j]=a;break;
                    }
                }
                min_d[b] = min_d[a]+matrix[a][b] ;
            }
         }
    }
}
 
void If_exist(int endpoint)
{
    /*這個副程式用來判斷使否有路徑，若沒有直接結束程式
    若有責開始判斷題目要求*/
    if(min_d[endpoint] == 1e9)
    {
        cout<<"沒有找到"<= 0 ; row_num--)
        //{
            for(int i = 0;i<length[row];i++)
            {
                calculate_path(startpoint,parent[endpoint][i],parent[endpoint][i]);
            }
        //}
    }
}
 
void other_path(int startpoint,int endpoint) //計算其他路徑的
{
    if(endpoint == startpoint)
    {return;}
    else
    minpathvalue = minpathvalue+matrix[(parent[endpoint][0])][endpoint];
    other_path(startpoint,parent[endpoint][0]);
}
 
void printPath(char startpoint, char endpoint, int before[], int len,int row) //印出路徑
{
    /*
    *查找?源?v到??u的路?，并?出
    *原理:一般的DisjointSet查找做變化，當某個點有兩個以上的Parent時，第二個Parent開始要將前一個的路徑補完整並且換行。
    *before陣列用來記錄前面的路徑資訊，用來補足路徑資訊時會用到，len代表最小路徑樹的level值
    */
    if (endpoint == startpoint) {
       //cout<<startpoint+65; 
        /*本來用cout無法輸出英文字母 需要把他轉成char型態的輸出
        但是不知道怎麼轉 就想說值街用回printf %C這樣最方便*/
        printf("%c",startpoint+'A');
        return ;
    }
    before[len] = endpoint;
    for (int i = 0 ; i  0) {
            for (int j = len - 1  ; j >= 0 ; --j) {
                //cout<"<%c",before[j]+'A');
            }
            cout<<endl;
        }
        printPath( startpoint, parent[endpoint][i], before, len + 1, parent[endpoint][i]);
        //cout<"<%c",endpoint+'A');
    }
}
 
int main()
{
    freopen("DS4.txt","r",stdin);
    freopen("Ans4.txt","w",stdout);
    build_matrix();
    dijkstra(start_point);
    if(If_exist)
    {
        length = new int [node];
        for(int i = 0;i<node;i++)
        {
            length[i] = 0;
            for(int j = 0;j<node;j++)
            {
                if(parent[i][j]==-1)break;
                else
                {
                    length[i] = length[i]+1;
                }
            }
        }
        calculate_path(start_point,end_point,end_point);
        cout<<pathnum<<endl;
        other_path(start_point,end_point);
        cout<<minpathvalue<<endl;
        int *before = new int [node];//紀錄路徑資訊
        printPath(start_point,end_point,before,0,end_point);
    }
 
}