Status AddCity(City *C){//增加
    int i,j,flag = 1;
    char *tname[MAX_VERTEX_NUM];
    while(1){
        printf("input the city name[input_end to return]:  ");
        scanf("%s",&tname);
        if(strcmp(tname,"_end") == 0) break;
        for(i = 0;i < C->CityNum; i++)
            if(strcmp(C->name[i],tname) == 0){
                printf("the [%s] city is in dat:",C->name[i]);
                flag = 0;
                return;
            }
        if(flag == 1){
            C->CityNum = C->CityNum + 1;
            strcpy(C->name[C->CityNum - 1],tname);

            for(i = 0; i < C->CityNum; i++){
                C->arcs[i][C->CityNum - 1].TTime = INFINITY;
                C->arcs[i][C->CityNum - 1].TPrice = INFINITY;
                C->arcs[i][C->CityNum - 1].FTime = INFINITY;
                C->arcs[i][C->CityNum - 1].FPrice = INFINITY;
            }
            for(j = 0; j < C->CityNum - 1; j++){
                printf("input TTime,TPrice,FTime,FPrice[%s -> %s]:  ",C->name[C->CityNum - 1],C->name[j]);
                scanf("%d%d%d%d",&C->arcs[C->CityNum - 1][j].TTime,&C->arcs[C->CityNum - 1][j].TPrice,&C->arcs[C->CityNum - 1][j].FTime,&C->arcs[C->CityNum - 1][j].FPrice);
                if(C->arcs[C->CityNum - 1][j].TTime == 0){
                    C->arcs[C->CityNum - 1][j].TTime = INFINITY;
                    C->arcs[C->CityNum - 1][j].TPrice = INFINITY;
                    C->arcs[C->CityNum - 1][j].FTime = INFINITY;
                    C->arcs[C->CityNum - 1][j].FPrice = INFINITY;
                }
                C->arcs[j][C->CityNum - 1] = C->arcs[C->CityNum - 1][j];
            }
        }
      change = 1;
    }
}

Status DelCity(City *C){//刪除
    int i,j,k,n,error = 1;
    char *tname[MAX_VERTEX_NUM],*tname1[MAX_VERTEX_NUM];
    while(1){
        printf("del city or traffic way[ 1 or 2 ][ other num;return ]:  ");
        k = getchar();
        scanf("%d",&k);
        if(k == 1){
            printf("input the city name you want to del:  ");
            scanf("%s",&tname);
            for(i = 0;i < C->CityNum; i++)
                if(strcmp(C->name[i],tname) == 0){
                    for(j = i; j < C->CityNum; j++){
                        strcpy(C->name[j],C->name[j + 1]);
                        for(n = 0; n < C->CityNum; n++){
                            C->arcs[n][j] = C->arcs[n][j + 1];
                        }
                    }
                     for(j = i; j < C->CityNum; j++){
                        for(n = 0; n < C->CityNum; n++){
                            C->arcs[j][n] = C->arcs[j + 1][n];
                        }
                    }
                }
                C->CityNum = C->CityNum - 1;
                error = 0;
                change = 1;
            if(error == 1) ShowError(2);
         }
        else if(k == 2){
            printf("input two city name of the way:  ");
            scanf("%s%s",&tname,&tname1);

            for(i = 0;i < C->CityNum; i++)
                if(strcmp(C->name[i],tname) == 0)
                    for(j = 0;j < C->CityNum; j++)
                        if(strcmp(C->name[j],tname1) == 0){
                            C->arcs[i][j].TTime = INFINITY;
                            C->arcs[i][j].TPrice = INFINITY;
                            C->arcs[i][j].FTime = INFINITY;
                            C->arcs[i][j].FPrice = INFINITY;
                            C->arcs[j][i] = C->arcs[i][j];
                            error = 0;
                            change = 1;
                        }
            if(error == 1) ShowError(2);
        }
        else break;
    }
}

Status EditCity(City *C){//修改
    int i,j,k,error = 1;
    char *tname[MAX_VERTEX_NUM],*tname1[MAX_VERTEX_NUM];
    while(1){
        printf("change name or traffic[ 1 or 2 ][ other num;return ]:  ");
        scanf("%d",&k);
        if(k == 1){
            printf("input the city name you want to change:  ");
            scanf("%s",&tname);
            for(i = 0;i < C->CityNum; i++)
                if(strcmp(C->name[i],tname) == 0){
                    printf("input the new name[%s]:",C->name[i]);
                    scanf("%s",C->name[i]);
                    change = 1;
                    error = 0;
                }
            if(error == 1) ShowError(2);
        }
        else if(k == 2){
            printf("input two city name of the way you want del:  ");
            scanf("%s%s",&tname,&tname1);

            for(i = 0;i < C->CityNum; i++)
                if(strcmp(C->name[i],tname) == 0)
                    for(j = 0;j < C->CityNum; j++)
                        if(strcmp(C->name[j],tname1) == 0){
                            printf("input new TTime,TPrice,FTime,FPrice [%s->%s]: ",C->name[i],C->name[j]);
                            scanf("%d%d%d%d",&C->arcs[i][j].TTime,&C->arcs[i][j].TPrice,&C->arcs[i][j].FTime,&C->arcs[i][j].FPrice);
                            C->arcs[j][i] = C->arcs[i][j];
                            error = 0;
                            change = 1;
                        }
            if(error == 1) ShowError(2);
        }
        else break;
    }
}

Status ShortestPath(City *C){//最小路徑
    int i,k,error = 1;
    char *tname[MAX_VERTEX_NUM];
    printf("input the frist city name and type[1 by TTime,2 by TPrice,3 by FTime,4 by FPrice]: \n");
    printf("input as [name,0] to show city name!\n");
    scanf("%s%d",&tname,&k);
    if(k < 1 || k > 4) ShowCityName(C,k);
    else{
        for(i = 0;i < C->CityNum; i++)
            if(strcmp(C->name[i],tname) == 0){
                error = 0;
                ShortestPath_DIJ(C,i,k);
            }
        if(error == 1) ShowError(2);
    }
}

Status ShortestPath_DIJ(City *C,int v0,int k){// 求源點v0到各點的最短路徑 1火車時間最小,2火車金錢最小,3飛機時間最小,4飛機金錢最小,
    int D[MAX_VERTEX_NUM],final[MAX_VERTEX_NUM],i,w,v=0,min;
    LinkQueue Q[MAX_VERTEX_NUM];// 建立隊列數組，用以依次儲存最短的路徑
    for(i = 0; i < C->CityNum; ++i){// 初始化數組
        InitQueue(&Q[i]);
        if(k == 1)D[i] = C->arcs[v0][i].TTime;
        if(k == 2)D[i] = C->arcs[v0][i].TPrice;
        if(k == 3)D[i] = C->arcs[v0][i].FTime;
        if(k == 4)D[i] = C->arcs[v0][i].FPrice;
        final[i] = false;
    }
    final[v0] = true;

    for(i = 1;i < C->CityNum; ++i){// 一個一個循環找出最短距離（共CityNum－1個）
        min = INFINITY;
        for(w = 0;w < C->CityNum; ++w){// 掃描找出非final集中最小的D[]
            if(!final[w] && D[w] < min){
                v = w;
                min = D[w];
            }
        }
        final[v] = true;

        for(w = 0;w < C->CityNum; ++w){// 更新各D[]數據
            if(k == 1) if(!final[w] && C->arcs[v][w].TTime + min < D[w]){
                D[w] = C->arcs[v][w].TTime + min;
                CopyQueue(&Q[v],&Q[w]);
                EnQueue(&Q[w],v);
            }
            if(k == 2) if(!final[w] && C->arcs[v][w].TPrice + min < D[w]){
                D[w] = C->arcs[v][w].TPrice + min;
                CopyQueue(&Q[v],&Q[w]);
                EnQueue(&Q[w],v);
            }
            if(k == 3) if(!final[w] && C->arcs[v][w].FTime + min < D[w]){
                D[w] = C->arcs[v][w].FTime + min;
                CopyQueue(&Q[v],&Q[w]);
                EnQueue(&Q[w],v);
            }
            if(k == 4) if(!final[w] && C->arcs[v][w].FPrice + min < D[w]){
                D[w] = C->arcs[v][w].FPrice + min;
                CopyQueue(&Q[v],&Q[w]);
                EnQueue(&Q[w],v);
           }
        }
    }

  // 打印出結果
    printf("frist -> end \t last \t\tthe-way\n\n");
    for(i  =0;i < C->CityNum; i++){
        if(D[i] != INFINITY){
            printf("%5s -> %s\t%d \t\t%s",C->name[v0],C->name[i],D[i],C->name[v0]);
            while(!EmptyQueue(&Q[i])){
                DeQueue(&Q[i],v);
                printf(" -> %s",C->name[v]);
            }
            printf(" -> %s\n",C->name[i]);
        }
        else{
            printf("%5s -> %s\tNo path!\n",C->name[v0],C->name[i]);
        }
   }
}

Status LoadCity(City *C){// 載入數據
    FILE *fp; // 文件指針
    char jian;
    int flag = 1;
    fp = fopen("City.city","rb");
    if(fp == NULL){
        printf("\ndate file is not find,buding?(y/n)\n");
        scanf("%c",&jian);
        if(jian == 'y'||jian == 'Y') fp = fopen("City.city","wb");
        else ShowError(1);
    }
    printf("\n=====>file is find,opening...\n");
    if(fread(C,sizeof(City),1,fp) != 1) flag = 0;
    if(flag){
        printf("\n=====>finish.\n");
        change = 0;
        }
     fclose(fp); // 關閉文件  
}

Status SaveCity(City *C){//  保存數據
    FILE* fp;
    int flag = 1;
    fp=fopen("City.city","wb");
    if(fp == NULL) ShowError(1);
    if(fwrite(C,sizeof(City),1,fp) != 1) flag = 0;
    if(flag){
        printf("\n=====>finish.");
        change = 0;
        }
    fclose(fp);
}

Status ShowCityDat(City *C){//顯示圖
    int k;
    printf("input show dat type[ 1TTime,2TPrice,3FTime,4FPrice ]:");
    scanf("%d",&k);
    if(k > 0 && k < 5) ShowCityName(C,k);
    else ShowError(2);
}

Status ShowCityName(City *C,int k){//顯示城市名與相應矩陣
    int i,j;
    if(k < 1 || k > 4) for(i = 0;i < C->CityNum; i++) printf("%6s  ",C->name[i]);
    else{
        printf("      ");
        for(i = 0;i < C->CityNum; i++) printf("%6s  ",C->name[i]);
        printf("\n");
        for(i = 0;i < C->CityNum; i++){
            printf("%6s  ",C->name[i]);
            for(j = 0;j < C->CityNum; j++){
                if(C->arcs[i][j].TTime == INFINITY) printf("   -\t");
                else{
                    if(k == 1)printf("%4d\t",C->arcs[i][j].TTime );
                    if(k == 2)printf("%4d\t",C->arcs[i][j].TPrice );
                    if(k == 3)printf("%4d\t",C->arcs[i][j].FTime );
                    if(k == 4)printf("%4d\t",C->arcs[i][j].FPrice );
                }
            }
            printf("\n");
        }
    }
}

Status ShowError(int k){//顯示錯誤
    switch(k){
        case 0:printf("\nMemory Failure！\nplease any key exit!");getch();exit(0);break;
        case 1:printf("\nfile error!\nplease any key exit!");getch();exit(0);break;
        case 2:printf("\ninput city not find!\n");break;
        default:getchar();break;
    }
}

Status showmenu(){//顯示目錄
    printf("\n1:ShowCityDat");
    printf("\n2:AddCity");
    printf("\n3:CreateCity");
    printf("\n4:EditCity");
    printf("\n5:DelCity");
    printf("\n6:ShortestPath");
    printf("\n7:LoadCity");
    printf("\n8:SaveCity");
    printf("\n0:exit\n");
}

main(){
    City *C;
    int set;
    char ch;
    if(!(C = (City *)malloc(sizeof(City)))) ShowError(0);

    LoadCity(C);
    while(1){
        showmenu();
        printf("please input the menu:");
        scanf("%d",&set);
        if(set == 0){
            if(change == 1){
                getchar();
                printf("\n=====>the dat is changed,save?(y/n)?\n");
                scanf("%c",&ch);
                if(ch=='y'||ch=='Y')
                SaveCity(C);
            }
            break;
        }
        switch(set){
            case 1:ShowCityDat(C);break; // 增加
            case 2:AddCity(C);break; // 增加
            case 3:CreateCity(C);break;//重來
            case 4:EditCity(C);break;// 修改
            case 5:DelCity(C);break;//刪除
            case 6:ShortestPath(C);break;// 查看
            case 7:LoadCity(C);break;//載入文件
            case 8:SaveCity(C);break;// 保存
            default: getchar();break;
        }
    }
}