will Dijkstra's shortest path do? modify the graph such that the edge from i to j V[i][j](transportation cost) now include the cost in vertex j (except when j is the destination).
On 5/1/07, mukesh tiwari <[EMAIL PROTECTED]> wrote: > > hello friends i m trying to solve problem > http://online-judge.uva.es/p/v5/523.html > > in this problem i using floyd's algorithm i m able to figure out total > cost but i m not able to figure out the path . may be the reason that i did > not understand the algorithm fully and i use it as a black box but now i > have to go inside blackbox so plz help me to figure out the path... > here is my code ... > > #include<iostream> > using namespace std; > #define inf 1000000 > int pathcost[1000][1000],pre[1000][1000]; > int takeinput() > { > int j,k=0,m; > char c; > while(cin.get(c) && c!='\n') > { > if((c>='0' && c<='9') || (c=='-')) > { > cin.unget(); > cin>>pathcost[0][k]; > if(pathcost[0][k]==-1) > pathcost[0][k]=inf; > k++; > } > } > return(k); > } > > > > int main() > { > int m1,citytax[1000],w,i,j,k,t1,t2; > char c; > > scanf("%d",&m1); > getchar();//one for \n and anthor for blank line > getchar(); > while(m1--) > { > w=takeinput(); > //printf("w=%d\n",w); > for( i=1;i<w;i++) > for( j=0;j<w;j++) > { > cin>>pathcost[i][j]; > if(pathcost[i][j]==-1) > pathcost[i][j]=inf; > } > > for(i=0;i<w;i++) > cin>>citytax[i]; > > getchar(); > > for(i=0;i<w;i++) > for(j=0;j<w;j++) > pre[i][j]=i; > > for(k=0;k<w;k++) > { > for(i=0;i<w;i++) > { > for(j=0;j<w;j++) > { > > if(pathcost[i][j]>pathcost[i][k]+pathcost[k][j]+citytax[k]) > { > > pathcost[i][j]=pathcost[i][k]+pathcost[k][j]+citytax[k]; > pre[i][j]=pre[k][j]; > } > } > } > } > > while(cin.get(c) && c!='\n') > { > cin.unget(); > cin>>t1>>t2; > printf("From %d to %d :\n",t1,t2); > printf("Total cost : %d\n",pathcost[t1-1][t2-1]); > getchar(); > } > printf("\n"); > > } > } > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
