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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
