数据结构习题(5)

stack.pop(); if((i!=strlen(a)-1))putchar(' '); }stack.push(a[i]); } } } int sign=0; while(!stack.isEmpty()){ if(!sign){ printf(\ sign=1; }else printf(\ stack.pop(); } putchar('\\n'); return 0; }

算法与数据结构题 实验题 7.1 参加婚礼 ★ 实验任务

小峰要结婚了，准备请他的大学同学来参加婚礼。他准备请一些同学参加自 己的婚礼，他们都在不同的城市。一共有 m 条路，每条路都有自己的花费，由 于大家来参加小峰的婚礼，来回的路费用自然是小峰报销啦。他希望每个同学都 能尽量给自己省钱。现在小峰想知道那些同学中谁需要的路费最多。 ★ 数据输入

输入第一行包括四个整数，N,M,P。N 表示一共有 N 个城市（编号 1-N），P 代表小峰所在城市的编号。

接下来 M 行每行两个整数 a，b，c 表示从 a 到 b 需要花费 c。 ★ 数据输出

输出一个整数表示那些同学中最大的花费。 输入示例 输出示例 4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3 10

★ ★Hint

题中的边均为单向边。 存在重边。

#include #include #include

typedef struct node *link; typedef struct node{ int e; link next; }NODE;

/*dj->把边反向->dj*/ int N,M,P,result=-1,flag=0; int dist[1001][2]; int a[1001][1001]; int prev[1001]={0};

link newnode(int x) { link p=(link)malloc(sizeof(NODE)); p->e=x; p->next=0; return p; }

link first=0;

void insert(int x) { if(first){ link p=newnode(x); link q=first->next; p->next=q; first->next=p; } else first=newnode(x); }

int delmin(void) { int x; link p=first,q=p->next,t=p,r=t; if(first->next==0){ x=first->e; first=0;

return x; } while(q){ if(dist[q->e][flag]e][flag]){t=p;r=q;} p=q; q=q->next; } if(t==r)first=r->next; else t->next=r->next; x=r->e; return x; }

void dj(void) { int i,j; for(i=1;i<=N;i++){ dist[i][flag]=a[P][i]; if(dist[i][flag]!=-1){ prev[i]=P; insert(i); } } dist[P][flag]=0; while(first){ i=delmin(); for(j=1;j<=N;j++){ if(a[i][j]!=-1&&(!prev[j]||dist[j][flag]>dist[i][flag]+a[i][j])) { dist[j][flag]=dist[i][flag]+a[i][j]; if(!prev[j])insert(j); prev[j]=i; } } } }

void djb(void) { int i,j; for(i=1;i<=N;i++){ dist[i][flag]=a[i][P]; if(dist[i][flag]!=-1){ prev[i]=P;

insert(i); } } dist[P][flag]=0; while(first){ i=delmin(); for(j=1;j<=N;j++){ if(a[j][i]!=-1&&(!prev[j]||dist[j][flag]>dist[i][flag]+a[j][i])) { dist[j][flag]=dist[i][flag]+a[j][i]; if(!prev[j])insert(j); prev[j]=i; } } } }

int main(void) {

int x,y,z,i,j;

scanf(\ memset(a,-1,sizeof(a)); for(i=1;i<=M;i++) {

scanf(\

if(a[x][y]==-1||a[x][y]>z) a[x][y]= z; } dj(); flag++;

memset(prev,0,sizeof(prev)); first=0; djb();

for(i=1;i<=N;i++){

// printf(\ if(dist[i][0]!=-1&&dist[i][1]!=-1) { if(dist[i][0]+dist[i][1]>result&&i!=P) result=dist[i][0]+dist[i][1]; } }

printf(\ return 0; }

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构习题(5)在线全文阅读。