Need effecient c program . Every intersection of a path has a red light on it i.

Question

Need effecient c program .

Every intersection of a path has a red light on it i.e: points marked A, B, C, D, E, F, G, H, I, J, K, etc. have a red light. The red light stoppage time and the time that the car takes to travel each section of the road will be provided as input. Assuming that there is only one car on the entire map and the car has to stop at EVERY RED LIGHT (for the amount of time specified) you need to find the shortest time the car will take to reach from source to destination. The time for which the car stops at the first red light has to be included in the final answer. The time for which the car stops at the last red light is NOT supposed to be included in the final answer. For example, if the source is A and the destination is B, the final answer will include the amount of time the car stops at A but not at B. Input First line of the input contains number of test cases T. First fifteen lines of each test case consists of one integer each denoting the time for which the car has to stop at each red light in alphabetical order (i.e. 1st number would denote the stoppage-time at A, 2nd at B and so on). It will be followed by twenty-six lines, each containing two alphabets and one integer. The integer denotes the time taken by the car to cover the distance between the stretch of the road specified by the two alphabets. This is followed by two lines each containing a single alphabet which specifies the source (S) and destination (D) of the car.

Explanation / Answer

#include<stdio.h> #include<stdlib.h> typedef struct node { int vertex,weight; struct node * next; }node; int main() { int test; scanf("%d",&test); while(test--) { int i,j,v,e,k,t1,t2,t3; char x,y; node * arr[100]={NULL}; node * temp; v=15; e=26; int a[15]; for(i=0;i<15;i++) { scanf("%d",&a[i]); } for(i=0;i<26;i++) { char dummy; getchar(); scanf("%c",&x); getchar(); scanf("%c%d",&y,&t3); t1=x-'A'; t2=y-'A'; if(arr[t1]==NULL) { arr[t1]=malloc(sizeof(node)); arr[t1]->vertex=t2; arr[t1]->weight=t3+a[t1]; arr[t1]->next=NULL; } else { temp=arr[t1]; while(temp->next!=NULL) { temp=temp->next; } temp->next=malloc(sizeof(node)); temp=temp->next; temp->vertex=t2; temp->weight=t3+a[t1]; temp->next=NULL; } if(arr[t2]==NULL) { arr[t2]=malloc(sizeof(node)); arr[t2]->vertex=t1; arr[t2]->weight=t3+a[t2]; arr[t2]->next=NULL; } else { temp=arr[t2]; while(temp->next!=NULL) { temp=temp->next; } temp->next=malloc(sizeof(node)); temp=temp->next; temp->vertex=t1; temp->weight=t3+a[t2]; temp->next=NULL; } } int start,end; getchar(); scanf("%c",&x); getchar(); scanf("%c",&y); start=x-'A'; end=y-'A'; int dis[v]; int flag[v]; for(i=0;i<v;i++) dis[i]=99999999; for(i=0;i<v;i++) flag[i]=0; int min=999999999,rem; dis[start]=0; for(i=0;i<v;i++) { temp=arr[start]; min=99999999; flag[start]=1; while(temp!=NULL) { if(dis[temp->vertex]>(temp->weight+dis[start])) { dis[temp->vertex]=(temp->weight+dis[start]); } temp=temp->next; } for(j=0;j<v;j++) { if(flag[j]==0) { if(dis[j]<min) { rem=j; min=dis[j]; } } } start=rem; } printf("%d ",dis[end]); } return 0; } #include<stdio.h> #include<stdlib.h> typedef struct node { int vertex,weight; struct node * next; }node; int main() { int test; scanf("%d",&test); while(test--) { int i,j,v,e,k,t1,t2,t3; char x,y; node * arr[100]={NULL}; node * temp; v=15; e=26; int a[15]; for(i=0;i<15;i++) { scanf("%d",&a[i]); } for(i=0;i<26;i++) { char dummy; getchar(); scanf("%c",&x); getchar(); scanf("%c%d",&y,&t3); t1=x-'A'; t2=y-'A'; if(arr[t1]==NULL) { arr[t1]=malloc(sizeof(node)); arr[t1]->vertex=t2; arr[t1]->weight=t3+a[t1]; arr[t1]->next=NULL; } else { temp=arr[t1]; while(temp->next!=NULL) { temp=temp->next; } temp->next=malloc(sizeof(node)); temp=temp->next; temp->vertex=t2; temp->weight=t3+a[t1]; temp->next=NULL; } if(arr[t2]==NULL) { arr[t2]=malloc(sizeof(node)); arr[t2]->vertex=t1; arr[t2]->weight=t3+a[t2]; arr[t2]->next=NULL; } else { temp=arr[t2]; while(temp->next!=NULL) { temp=temp->next; } temp->next=malloc(sizeof(node)); temp=temp->next; temp->vertex=t1; temp->weight=t3+a[t2]; temp->next=NULL; } } int start,end; getchar(); scanf("%c",&x); getchar(); scanf("%c",&y); start=x-'A'; end=y-'A'; int dis[v]; int flag[v]; for(i=0;i<v;i++) dis[i]=99999999; for(i=0;i<v;i++) flag[i]=0; int min=999999999,rem; dis[start]=0; for(i=0;i<v;i++) { temp=arr[start]; min=99999999; flag[start]=1; while(temp!=NULL) { if(dis[temp->vertex]>(temp->weight+dis[start])) { dis[temp->vertex]=(temp->weight+dis[start]); } temp=temp->next; } for(j=0;j<v;j++) { if(flag[j]==0) { if(dis[j]<min) { rem=j; min=dis[j]; } } } start=rem; } printf("%d ",dis[end]); } return 0; }

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.