am using Dijkstra's algorithm for www.spoj.pl/TSHPATH
I'm getting WA.
someone plz help me..
#include<iostream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<map>
using namespace std;
struct val{
int from;
int to;
};
bool operator <(val a, val b){
if(a.from==b.from)
return a.to<b.to;
else
return a.from<b.from;
}
map <val , int> soln;
map< val, bool> flags;
map< string, int> INDEX;
struct COST{
int from;
int to;
};
bool operator <(COST a, COST b){
if(a.from==b.from)
return a.to<b.to;
else
return a.from<b.from;
}
map< COST, int> Cost;
struct N{
int n;
int * neigh;
};
bool operator <(N a, N b){
return a.neigh<b.neigh;
}
map< int, N> neighbour;
map<int, bool> visited;
int find(int from,int to,int n){
visited.clear();
int min[10001];
for(int i=1;i<=n;i++)
min[i]=9999999;
min[from]=0;
for(int current=from;;){
// cout<<"current = "<<current<<endl;
if(current==to)
break;
N neighbours= neighbour[current];
for(int i=1;i<=neighbours.n;i++){
if( !visited[neighbours.neigh[i]] )
{
COST p;
p.from=current;
p.to=neighbours.neigh[i];
int temp=min[current]+Cost[p];
if(temp< min[ neighbours.neigh[i] ] )
min[neighbours.neigh[i]]=temp;
// cout<<"min["<<neighbours.neigh[i]<<"]="<<
// min[neighbours.neigh[i]]<<endl;
}
}
//choose minimum unvisited
int minn=9999999,minindex=9999999;
for(int i=1;i<=n;i++){
if(i!=current&&i!=from&&!visited[i]){
if(minn> min[i]){
minn=min[i];
minindex=i;
}
}
}
if(minindex==9999999){
// for(int i=1;i<=n;i++)
// cout<<min[i]<<" ";
cout<<endl;
cout<<endl;
return min[to];
}
visited[current]=1;
current=minindex;
}
// for(int i=1;i<=n;i++)
// cout<<min[i]<<" ";
//cout<<endl;
//cout<<endl;
return min[to];
}
int *nr;
map<int *, bool> addressflag;
int main(){
int s,n,p,cost,t;
string name,from,to;
scanf("%d",&s);
while(s--){
scanf("%d",&n);
addressflag.clear();
INDEX.clear();
Cost.clear();
flags.clear();
soln.clear();
neighbour.clear();
for(int i=1;i<=n;i++)
{
addressflag[nr]=1;
again:
delete(nr);
nr=new int[10001];
if(addressflag[nr]==1)
goto again;
cin>>name;
INDEX[name]=i;
scanf("%d",&p);
for(int j=1;j<=p;j++){
scanf("%d",&nr[j]);
scanf("%d",&cost);
COST a;
a.from=i;
a.to=nr[j];
Cost[a]=cost;
}
N abc;
abc.n=p;
abc.neigh=nr;
neighbour[i]=abc;
}
/* for(int i=1;i<=n;i++)
{
cout<<"neighbours of "<<i<<" are ";
N all=neighbour[i];
for(int j=1;j<=all.n;j++)
cout<<all.neigh[j]<<" ";
cout<<endl;
}
*/
scanf("%d",&t);
while(t--){
cin>>from>>to;
cout<<find(INDEX[from],INDEX[to],n)<<endl;
}
}
return 0;
}
--
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?hl=en.
