1    2   3 #include<stdio.h>  4 #include<string.h>  5 #include<string>  6 #include<iostream>  7 using namespace std;  8 typedef struct Tree{    //表示图的数据结构  9     int weight[36][36]; //权值 10     int mark[36];       //是否访问标记 11     int result[36];     //某站到所有站的最短距离（结果存储） 12 }Tree; 13  14 void init(Tree &train)  //生成相对应的图，初始化 15 { 16     int i,j; 17     for (i=1; i <= 36; i++) 18         for (j=1; j<= 36; j++) 19             if (i == j) 20                 train.weight[i][j] = 0; 21             else 22                 train.weight[i][j] = 65535; 23     // A路线 24     for (i=1; i <= 8; i++){ 25             train.weight[i][i+1] = 1; 26             train.weight[i+1][i] = 1; 27     } 28     for (i=10; i <= 12; i++){ 29             train.weight[i][i+1] = 1; 30             train.weight[i+1][i] = 1; 31     } 32     for (i=14; i <= 17; i++){ 33             train.weight[i][i+1] = 1; 34             train.weight[i+1][i] = 1; 35     } 36     train.weight[18][1] = 1; 37     train.weight[1][18] = 1; 38     // B路线 39     for (i=19; i <= 22; i++){ 40             train.weight[i][i+1] = 1; 41             train.weight[i+1][i] = 1; 42     } 43     for (i=24; i <= 27; i++){ 44             train.weight[i][i+1] = 1; 45             train.weight[i+1][i] = 1; 46     } 47     for (i=29; i <= 32; i++){ 48             train.weight[i][i+1] = 1; 49             train.weight[i+1][i] = 1; 50     } 51     //Ｔ１　Ｔ２ 52     train.weight[34][9] = 1; 53     train.weight[9][34] = 1; 54     train.weight[34][10] = 1; 55     train.weight[10][34] = 1; 56     train.weight[34][23] = 1; 57     train.weight[23][34] = 1; 58     train.weight[34][24] = 1; 59     train.weight[24][34] = 1; 60     train.weight[35][13] = 1; 61     train.weight[13][35] = 1; 62     train.weight[35][14] = 1; 63     train.weight[14][35] = 1; 64     train.weight[35][28] = 1; 65     train.weight[28][35] = 1; 66     train.weight[35][29] = 1; 67     train.weight[29][35] = 1; 68     for (i=1; i <= 36; i++) 69         train.mark[i] = 0; 70 } 71  72 //Dijkstra算法计算最短路径 73 int foo(int a, int b, Tree train) 74 { 75     int i,j,mi,m,k; 76     for (i=1; i <= 36; i++){ 77         train.result[i] = train.weight[a][i]; 78         //printf("%d ",train.result[i]); 79     } 80     //printf("\n"); 81     train.mark[a] = 1; 82     for (i=1; i <= 36; i++) 83         { 84             mi = 65535; 85             for (j=1; j <= 36; j++){                                        //搜寻当前未访问的最短路径(作为下一访问点） 86                 if (!train.mark[j] && train.result[j] < mi) 87                 { 88                     m = j; 89                     mi = train.result[j]; 90                 } 91             } 92             for (k=1; k <= 36; k++){                                        //比较（经过当前访问点的距离）与之前最短路径的距离 93                 if (train.result[m] + train.weight[m][k] < train.result[k]) 94                     train.result[k] = train.result[m] + train.weight[m][k]; //比之前的则更新 95                 } 96             train.mark[m] = 1; 97  98         } 99     for (i=1; i <= 35; i++){                                                //结果输出100         printf("%4d ",train.result[i]);101     }102     printf("\n");103     return train.result[b]+1;104 }105 106 int main()107 {108     string abt[] = {"A1", "A2", "A3", "A4", "A5", "A6", "A7", "A8", "A9", "A10", "A11", "A12", "A13", "A14", "A15", "A16", "A17", "A18",109     "B1", "B2", "B3", "B4", "B5","B6", "B7", "B8", "B9", "B10", "B11", "B12", "B13", "B14", "B15", "T1", "T2"};110     char s1[10],s2[10];111     int a,b,i;112     Tree train;113     init(train);114     scanf("%s%s",s1,s2);115     for (i=0; i < 36; i++)116     {117         if (strcmp(s1,abt[i].c_str()) == 0)118             a = i;119         if (strcmp(s2,abt[i].c_str()) == 0)120             b = i;121     }122     printf("%d %d\n",a+1,b+1);123     printf("到相对应站的距离：\n");124     for (i=1; i <= 35; i++){125         printf("%4s ",abt[i-1].c_str());126     }127     printf("\n");128     printf("\n最后结果：%d\n",foo(a+1,b+1,train));129 130 }131