#define INFINITY 10000
#define MAX_VERTEX_NUM 32
#define MAX_ARC_NUM 50
#include<stdio.h>
#include<string.h>

typedef struct{
    int v;
    char city[20];
}VertexType;

typedef struct {
    VertexType vex[MAX_VERTEX_NUM];
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
    int vexnum,arcnum;
}MGraph;

typedef int ShortPathTable[MAX_VERTEX_NUM];
typedef int PathMatrix[MAX_VERTEX_NUM];


void CreateDG(MGraph &G){
        int i,j;
        char string[][20]={"Beijing","Haerbin","Changchun","Shenyang","Tianjin","Dalian","HHHT","Yinchuan",
                       "WLMQ","Xining","Lanzhou","Xi'an","Taiyuan","Zhengzhou","Xuzhou","Shanghai",
                       "Nanjing","Hefei","Wuchang","Changsha","Chongqinh","Chengdu","Kunming","Guiyang",
                       "Zhuzhou","Nanchang","Hangzhou","Fuzhou","Shenzhen","Guangzhou","Liuzhou","Nanning"
                      };
        G.vexnum=MAX_VERTEX_NUM;
        G.arcnum=MAX_ARC_NUM;

        for(i=0;i<G.vexnum;++i)
            for(j=0;j<G.vexnum;++j)
                G.arcs[i][j]=INFINITY;

       for(i=0;i<MAX_VERTEX_NUM;i++)strcpy(G.vex[i].city,string[i]);
      
    FILE *fp;
    char filename[10];
    int ch;
    fp=fopen("graph.dat","r");
    ch=fgetc(fp)-48;
    while(!feof(fp)){
        int i=0,j=0;
        
        if(ch!=0)i=10*ch;
        ch=fgetc(fp)-48;
        i=i+ch;

        ch=fgetc(fp)-48;
        if(ch!=0)j=10*ch;
        ch=fgetc(fp)-48;
        j=j+ch;

        G.arcs[i][j]=0;
        ch=fgetc(fp)-48;
        if(ch!=0)G.arcs[i][j]=1000*ch;
        ch=fgetc(fp)-48;
        G.arcs[i][j]+=100*ch;
        ch=fgetc(fp)-48;
        G.arcs[i][j]+=10*ch;
        ch=fgetc(fp)-48;
        G.arcs[i][j]+=ch;
        ch=fgetc(fp)-48;
    }

      
}

   

void ShortestPath_DIJ(MGraph G,int v0,PathMatrix &P,ShortPathTable &D){
    int v,w,i,min;
    bool final[MAX_VERTEX_NUM];   

    for(w=0;w<MAX_VERTEX_NUM;w++)P[w]=-1;
    for(v=0;v<G.vexnum;++v){
        final[v]=false;
        D[v]=G.arcs[v0][v];
        if(D[v]<INFINITY)P[v]=v0;   
    }

    D[v0]=0;
    final[v0]=true;
    for(i=1;i<G.vexnum;++i){
        min=INFINITY;
        for(w=0;w<G.vexnum;++w)
            if(!final[w])
                if(D[w]<min){
                    v=w;
                    min=D[w];
                }

         final[v]=true;

         for(w=0;w<G.vexnum;++w)
             if(!final[w]&&(min+G.arcs[v][w]<D[w])){
                 D[w]=min+G.arcs[v][w];
                 P[w]=v;
                 
             }
    }
}

void Output_ShortestPath(MGraph G,int v0,int vn,PathMatrix P,ShortPathTable D){
    printf("from(%d)%sto(%d)%sthe shortest line%dkm。\n\t",v0,G.vex[v0].city,vn,G.vex[vn].city,D[vn]);
    printf("zhe shortest line is:");
   
    int t;
    int i;
    int a[MAX_VERTEX_NUM];
    printf("%s-->",G.vex[v0].city);
    for(i=0;i<MAX_VERTEX_NUM;i++)a[i]=-1;
   
    for(t=P[vn],i=MAX_VERTEX_NUM-1;(t!=-1)&&(t!=v0);i--){
        a[i]=t;
        t=P[t];
    }

    for(i=0;i<MAX_VERTEX_NUM;i++){
        if(a[i]==-1)i++;
        else printf("%s-->",G.vex[a[i]].city);
    }
        printf("%s",G.vex[vn].city);
}



void main()
{
    int v0,vn,ch=1;
    ShortPathTable D;
    PathMatrix P;
    MGraph G;
    printf("  \t\t\tmap is aready loaded graph relative city");
    printf("\n ****************************************************************************\n");
    printf("\t0Beijing\t1Haerbin\t2Changchun\t3Shenyang\n\t4Tianjin\t5Dalian\t6HHHT\t7Yinchuan\n\t8WLMQ\t9Xining\t10Lanzhou\t11Xian\n\t12Taiyuan\t13Zhengzhou\t14Xuzhou\t15Shanghai\n\t16Nanjing\t17Hefei\t18Wuchang\t19Changsha\n\t20Chongqinh\t21Chengdu\t22Kunming\t23Guiyang\n\t24Zhuzhou\t25Nanchang\t26Hangzhou\t27Fuzhou\n\t28Shenzhen\t29Guangzhou\t30Liuzhou\t31Nanning\n ");
       printf("****************************************************************************\n");
    printf("\n");
   
    CreateDG(G);
   
    while(ch){   
        printf("input zhe num of beginning city");  
        scanf("%d",&v0);
        printf("input zhe num of ending city");   
        scanf("%d",&vn);   
        ShortestPath_DIJ(G,v0,P,D);
        printf("\n****************************************************************************\n");
        Output_ShortestPath(G,v0,vn,P,D);
        printf("\n*****************************************************************************\n");

        printf("\n\n");   
        printf("1 for continue\t0 for exit");   
        printf("\n");   
        scanf("%d",&ch);
   
    }

   
}