【问题描述】
编写一个程序实现北京地铁最短乘坐（站）线路查询，输入为起始站名和目的站名，输出为从起始站到目的站的最短乘坐站换乘线路。注：1. 要求采用Dijkstra算法实现；2）如果两站间存在多条最短路径，找出其中的一条就行。
【输入形式】
文件bgstations.txt为数据文件（可从课程网站中课程信息处下载），包含了北京地铁的线路及车站信息。其格式如下：
<地铁线路总条数>
<线路1> <线路1站数>
<站名1> <换乘状态>
<站名2> <换乘状态>
…
<线路2> <线路2站数>
<站名1> <换乘状态>
<站名2> <换乘状态>
…
说明：文件第一行为地铁总线路数；第二行第一个数为某条地铁线线号（如，1为1号线），第二个数为该条地铁线的总站数（如1号线共有23站），两数之间由一个空格分隔；第三行两个数据分别为地铁站名及换乘状态（0为非换乘站，1为换乘站），两数据间由一个空格分隔；以下同，依次为该线地铁其它站信息。在一条线路信息之后是下条地铁线路信息，格式相同。若某条地铁线为环线，则首站与末站信息相同（如北京地铁2号线，首站信息“西直门 1” ，末站信息为“西直门 1”）。例如本题提供的bgstations.txt文件（可从课程网站中课程信息处下载）内容如下：
13
1 23
苹果园 0
古城 0
八角游乐园 0
八宝山 0
玉泉路 0
五棵松 0
万寿路 0
公主坟 1
军事博物馆 1
木樨地 0
南礼士路 0
复兴门 1
西单 1
…
2 19
西直门 1
积水潭 0
鼓楼大街 1
…
西直门 1
…
该文件表明当前北京地铁共有13条线路（不含郊区线路），接着为每条线路信息。
打开当前目录下文件bgstations.txt，读入地铁线路信息，并从标准输入中读入起始站和目的站名（均为字符串，各占一行）。
【输出形式】
输出从起始站到目的站的乘坐信息，要求乘坐站数最少。换乘信息格式如下：
SSN-n1(m1)-S1-n2(m2)-…-ESN
其中：SSN和ESN分别为起始站名和目的站名；n为乘坐的地铁线路号，m为乘坐站数。
【样例输入】
西土城
北京西站
【样例输出】
西土城-10(1)-知春路-13(2)-西直门-4(2)-国家图书馆-9(4)-北京西站
（或西土城-10(1)-知春路-13(2)-西直门-2(1)-车公庄-6(2)-白石桥南-9(3)-北京西站）
【样例说明】
打开文件bgstations.txt，读入地铁线路信息，并从标准输入中读入查询起始站名为“西土城”，目的站名为“北京西站”。程序运行结果两站间最少乘坐站数的乘坐方式为“西土城站乘坐10号线1站至知春路站换乘13号线乘坐2站至西直门站换乘4号线乘坐2站至国家图书馆站换乘9号线乘坐4站至北京西站”。本样例存在两条最少站数的乘坐方式，只要找出一条就可以。
代码1
#include <stdio.h>#include <stdlib.h>#include <string.h>#define N 1005int n, a[15], k = 0, tot = 0, head[N];char s[25], s1[25], s2[25], name[N][25];struct NODE{int from, to, next, id;} e[N];int find(char s[]){int i;int t = -1;for (i = 1; i <= tot; i++)if (strcmp(s, name[i]) == 0){t = i;break;}return t;}void add(int x, int y, int z){e[++k].to = y;e[k].next = head[x];e[k].id = z;e[k].from = x;head[x] = k;}int d[N], q[N * 10], v[N], from[N], ans[N];void spfa(int xx, int yy){int i;for (i = 1; i <= tot; i++)d[i] = 100000;d[xx] = 0;q[1] = xx;v[xx] = 1;int l = 1, r = 1;while (l <= r){int x = q[l++];v[x] = 0;i = head[x];while (i){if (d[e[i].to] > d[x] + 1){d[e[i].to] = d[x] + 1;from[e[i].to] = i;if (!v[e[i].to]){v[e[i].to] = 1;q[++r] = e[i].to;}}i = e[i].next;}}tot = 0;while (yy != xx){ans[++tot] = from[yy];yy = e[from[yy]].from;}printf("%s", name[xx]);int num = 0;for (i = tot; i >= 1; i--){if (i != tot && e[ans[i]].id != e[ans[i + 1]].id){printf("-%d(%d)-%s", e[ans[i + 1]].id, num, name[e[ans[i]].from]);num = 1;}elsenum++;}printf("-%d(%d)-%s\n", e[ans[1]].id, num, name[e[ans[1]].to]);}int main(){FILE *fp = fopen("bgstations.txt", "r");fscanf(fp, "%d", &n);int i, j, x, y;for (i = 1; i <= n; i++){fscanf(fp, "%d%d", &x, &a[i]);int pre = -1;for (j = 1; j <= a[i]; j++){fscanf(fp, "%s%d", &s, &y);int t = find(s);if (t == -1){t = ++tot;strcpy(name[tot], s);}if (pre != -1){add(pre, t, x);add(t, pre, x);}pre = t;}}scanf("%s%s", s1, s2);int t1 = find(s1);int t2 = find(s2);spfa(t1, t2);return 0;}
Floyd算法
#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX 428#define SUP 256#define LIN 200struct hashone{char name[99];int next;} HB[MAX];struct simplify{char name[99];struct simplify *next;} * play[MAX][MAX];char from[99], to[99], pat[2][MAX][99];int Line, dis, min, buf, skip;int inl[LIN][MAX][MAX], sym[2][MAX][LIN], swl[2][MAX], Ans[LIN], isvertex[LIN];int i, j, k;int hash(char *, int), ctoh(char *);char *htoc(int);void ini(void), Floyd(int), linklist(void), output_route(void),sign(int, int, int);int hash(char *s, int m){unsigned int h = 0, a, se = 23, i;char *p;for (p = s; *p; p++)h = h * se + *p;h = h % SUP + 1;if (m){if (strlen(HB[h].name)){for (a = h; HB[a].next; a = HB[a].next);h = ++HB[0].next;HB[a].next = h;strcpy(HB[h].name, s);return h;}else{strcpy(HB[h].name, s);return h;}}for (; strcmp(HB[h].name, s) && h; h = HB[h].next);return h;}int ctoh(char *s) {return hash(s, 0) ? hash(s, 0) : hash(s, 1); }char *htoc(int h) {return HB[h].name; }void Floyd(int l){int i, j, k;for (k = 0; k < MAX; k++){for (i = 0; i < MAX; i++){for (j = 0; j < MAX; j++){if (i == j){inl[l][i][j] = 0;}else if ((inl[l][i][k] + inl[l][k][j] < inl[l][i][j])){inl[l][i][j] = inl[l][i][k] + inl[l][k][j];}}}}}void linklist(){for (k = 0; k < MAX; k++){for (i = 0; i < LIN; i++){if (sym[1][k][i]){for (j = 0; j < LIN; j++){if ((i != j) && (sym[1][k][j])){if (play[i][j]){struct simplify *p;for (p = play[i][j]; p->next; p = p->next);p->next = malloc(sizeof(struct simplify));p = p->next;p->next = NULL;strcpy(p->name, htoc(k));}else{play[i][j] = malloc(sizeof(struct simplify));play[i][j]->next = NULL;strcpy(play[i][j]->name, htoc(k));}}}}}}}void output_route(void){int f = ctoh(from), t = ctoh(to);buf = min = MAX;for (i = 0; i < MAX; i++)swl[0][i] = swl[1][i] = pat[0][i][0] = pat[1][i][0] = 0;for (i = 0; i < LIN; i++)isvertex[i] = 0;if (f != t){for (i = 0; i < LIN; i++)if (sym[0][f][i])for (j = 0; j < LIN; j++)if ((sym[0][t][j])){// printf ("%d-------------->%d\n",i,j);sign(i, j, 0);}int x = ctoh(from), y, l;printf("%s", from);for (i = 0; swl[0][i]; i++){l = swl[0][i];y = x;x = strlen(pat[0][i]) ? ctoh(pat[0][i]) : ctoh(to);printf("-%d(%d)-%s", l, inl[l][y][x], pat[0][i]);}printf("%s\n", to);}else{for (i = 0; i < LIN; i++){if (sym[0][f][i]){printf("%s-%d(0)-%s", from, i, from);return;}}}return;}void sign(int F, int T, int d){int i, j;swl[1][d] = F;isvertex[F] = 1;if ((d == 0) && (F == T)){isvertex[F] = 0;}if (d >= 6)return;for (i = 0; i < MAX; i++){if (play[F][i]){struct simplify *p = play[F][i];while (p){if (!isvertex[i]){strcpy(pat[1][d], p->name);sign(i, T, d + 1);swl[1][d + 1] = 0;isvertex[i] = 0;pat[1][d][0] = 0;}p = p->next;}}}if (F == T){int x = ctoh(from), y, l;skip = dis = 0;// printf ("%s",from);for (i = 0; swl[1][i]; i++){l = swl[1][i];y = x;x = strlen(pat[1][i]) ? ctoh(pat[1][i]) : ctoh(to);dis += inl[l][y][x];skip++;if (dis > min){return;}}if ((dis == min) && (skip > buf))return;buf = skip;min = dis;for (i = 0; swl[1][i]; i++){l = swl[0][i] = swl[1][i];strcpy(pat[0][i], pat[1][i]);swl[0][i + 1] = 0;pat[0][i + 1][0] = 0;}return;}return;}int main(){for (k = 0; k < LIN; k++){for (j = 0; j < MAX; j++){for (i = 0; i < MAX; i++)inl[k][i][j] = MAX;}}HB[0].next = SUP;strcpy(HB[0].name, "NULL");FILE *in = fopen("bgstations.txt", "r");char station[99], last[99];int ex, now, num, count;fscanf(in, "%d", &Line);while (~(fscanf(in, "%s %d", station, &ex))){if (atoi(station)){count = 0, now = atoi(station), num = ex;}else{int i = ctoh(last), j = ctoh(station);if (count){inl[now][i][j] = inl[now][j][i] = 1;}if (count == num - 1){Floyd(now);}if (ex){sym[1][j][now] = 1;}sym[0][j][now] = 1;count++;memcpy(last, station, 99);}}linklist();while (~(scanf("%s%s", from, to)))output_route();return 0;}
Dijkstra算法
#include <stdio.h>#include <string.h>#define max_length 10#define max_station 600#define INFINITY 99999struct station{char name[max_length]; // nameint transit;} sta[max_station]; // every stationstruct one{int wei;char line[15];} vertex[max_station + 5][max_station + 5];int k, spath[max_station]; // path storagevoid input(){FILE *in = fopen("bgstations.txt", "r");int max_line;fscanf(in, "%d", &max_line);int i, j, v1, v2;// initiatefor (i = 1; i <= max_station; i++){for (j = 1; j <= max_station; j++){vertex[i][j].wei = INFINITY;memset(vertex[i][j].line, 0, sizeof(vertex[i][j].line));}}for (i = 0; i <= max_line; i++){char line_num[15] = {0};int station_num = 0;v1 = v2 = -1; // station before, station after;fscanf(in, "%s%d", line_num, &station_num);for (j = 1; j <= station_num; j++){char s[max_station] = {0};int ii, flag = 1, change;fscanf(in, "%s%d", s, &change);for (ii = 1; ii <= k; ii++){if (strcmp(sta[ii].name, s) == 0){// have readflag = 0;v1 = ii;break;}}if (flag == 1){k++;memcpy(sta[k].name, s, 600);sta[k].transit = change;v1 = k;}if (v2 != -1){strcpy(vertex[v2][v1].line, line_num);strcpy(vertex[v1][v2].line, vertex[v2][v1].line);vertex[v1][v2].wei = vertex[v2][v1].wei = 1;}v2 = v1;}}fclose(in);}void Dijkstra(int origion, int arrival){int i, j, v = 0, minweight;int found[max_station + 5];// sign_lengthmemset(found, 0, sizeof(found)); // initiateint sweight[max_station + 5]; // nearestfor (i = 1; i <= max_station; i++){// initiatesweight[i] = vertex[origion][i].wei;spath[i] = origion; // before one}sweight[origion] = 0;found[origion] = 1; // have foundfor (i = 1; i < max_station; i++){// continue searchminweight = INFINITY;for (j = 1; j <= max_station; j++){if (!found[j] && sweight[j] < minweight){minweight = sweight[j];v = j;}}found[v] = 1;if (v == arrival)return;for (j = 1; j <= max_station; j++){if ((!found[j]) && (vertex[v][j].line > 0) &&(minweight + vertex[v][j].wei < sweight[j])){sweight[j] = minweight + vertex[v][j].wei;spath[j] = v;}}}}void output(int origion, int arrival){// �������Ҫ��spath������з����ȡint i = arrival, j = 1;int temp[max_station];for (i = arrival, j = 0; i != origion;){temp[++j] = spath[i];i = spath[i];}int flag = 0, count = 1;temp[0] = arrival;for (i = j; i >= 1; i--){if (flag == 0){printf("%s-%s", sta[temp[i]].name,vertex[temp[i]][temp[i - 1]].line);flag = 1;}else{if (strcmp(vertex[temp[i + 1]][temp[i]].line,vertex[temp[i]][temp[i - 1]].line) == 0)count++;else{printf("(%d)-", count);count = 1;flag = 0;i++;}}}printf("(%d)-%s\n", count, sta[arrival].name);}int main(){input();char start[max_length] = {0}, end[max_length] = {0};scanf("%s%s", start, end);int origion = 0, arrival = 0, count = 0;int i = 1;for (; i <= k; i++){if (strcmp(sta[i].name, start) == 0){origion = i;count++;}if (strcmp(sta[i].name, end) == 0){arrival = i;count++;}if (count == 2)break;}Dijkstra(origion, arrival);output(origion, arrival);return 0;}
BUAAer？
