蓝桥杯2011决赛c本科试题及答案

线2 西直门 车公庄 .... 建国门 线4 ....

其中第一行数据为地铁线名，接下来是该线的站名。 当遇到空行时，本线路站名结束。

下一行开始又是一条新线....直到数据结束。

如果多条线拥有同一个站名，表明：这些线间可以在该站换车。

为引导旅客合理利用线路资源，解决交通瓶颈问题，该城市制定了票价策略：

1. 每条线路可以单独购票，票价不等。

2. 允许购买某些两条可换乘的线路的联票。联票价格低于分别购票。

单线票价和联合票价如 price.txt 所示。

线1 180 .....

线13 114 线1,线2 350 线1,线10 390 .....

每行数据表示一种票价

线名与票价间用空格分开。如果是联票，线名间用逗号分开。 联票只能包含两条可换乘的线路。

现在的问题是：根据这些已知的数据，计算从A站到B站最小花费和可行的换乘方案。

比如，对于本题目给出的示例数据

如果用户输入： 五棵松,奥体中心

程序应该输出：

第 9/20 页

-(线1,线10)-线8 = 565

如果用户输入： 五棵松,霍营

程序应该输出：

-线1-(线4,线13) = 440

可以看出，用户输入的数据是：起始站，终到站，用逗号分开。

程序输出了购票方案，在括号中的表示联票，短横线(-)用来分开乘车次序。 等号后输出的是该方案的花费数值。

请编程解决上述问题。 注意：

1. 我们测试您的程序时，所用数据与题目中的示例数据不同，但格式完全一样。2. 当多个方案有相同的最小花费，输出任意一个方案即可。

要求考生把所有类写在一个文件中。

调试好后，存入与考生文件夹下对应题号的“解答.txt”中即可。 相关的工程文件不要拷入。请不要使用package语句。

#include using namespace std; #define LEN 50

typedef struct stations{ char name[20]; int len; int roads[50]; struct stations *left; struct stations *right; }Stations;

typedef struct etree{ int value; int roadNum; struct etree *father; int childnum; }ETree;

typedef struct queue{ ETree *tie;

第 10/20 页

struct queue *next; }Queue;

void pushQueue(Queue &head, ETree *&etree){ Queue *p=head.next,*q=&head; while(p!=NULL && (p->tie->valuevalue)){ q=p; p=p->next; } q->next=(Queue*)malloc(sizeof(Queue)); q->next->tie=etree; q->next->next=p; }

void freeEtree(ETree *q){ ETree *p; while(q->childnum==0){ p=q; q=q->father; free(p); if(q!=NULL) q->childnum--; else break; } }

void freeAll(Stations *&head){ if (head!=NULL){ freeAll(head->left); freeAll(head->right); free(head); } }

void showBest(ETree *h,int price[][LEN],char roadName[][20],int roadNum){ if(h!=NULL){ if (h->faher==NULL){ printf(\ } else{ int j; j=h->roadNum; if (h->value==(price[j][j]+h->father->value)){ showBest(h->father,price,roadName,roadNum);

第 页 11/20

if (price[j][roadNum]){ printf(\ } else printf(\ } else{ showBest(h->father->father,price,roadNme,roadNum); printf(\ } } } }

inline int compares(char s1[],int n1,chr s2[],int n2){ if (n1!=n2) return n1-n2; return strcmp(s1,s2); }

boll findStation(Stations* &head,Stations* &p,char s[]){ int len=strlen(s); int t; Stations q; p=head; while (n!=NULL){ q=p; t=compares(s,len,p->name,p->len); if (t<0) p=p->left; else retrn true; } p=q; return false; }

void insert(Stations* &head,char s[],int road,int price[][LEN]{ Stations *p,*q; int t; t=strlen(s); if(s[t-1]=='\\n') s[t-1]='\\0'; if(head==NULL){

第 12/20 页