## 10917 - Walk Through the Forest

Moderator: Board moderators

shantanu18
New poster
Posts: 22
Joined: Tue Jul 20, 2010 9:55 pm

### Re: 10917 - A Walk Through the Forest

Run dijkstra to calculate shortest path and dp to save the # of path. WA!!! please help

Code: Select all

``````#include <cstdio>
#include <iostream>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#define pa  pair <int,int>
#define MAX 1010
using namespace std;
vector <pa> v[MAX];
int ver,edg,e1,e2,wed,d[MAX],w[MAX],prev[MAX];
struct com{
bool operator () (const pa &a, const pa &b)
{
return a.second>b.second;
}
};
/*void _print(int node)
{
if(node==-1) return;
cout<<node+1<<"  "<<w[node]<<endl;
_print(prev[node]);
}*/
void dijkstra(int src)
{
priority_queue<pa,vector<pa>,com> Q;
memset(d,-1,sizeof(d));
memset(prev,-1,sizeof(prev));
memset(w,0,sizeof(w));
d[src]=0;
w[src]=1;
Q.push(pa(src,0));
while(!Q.empty())
{
pa t=Q.top();Q.pop();
for(int i=0;i<(int)v[t.first].size();i++)
{
if(d[t.first] + v[t.first][i].second < d[v[t.first][i].first] ||  d[v[t.first][i].first]==-1)
{
d[v[t.first][i].first] = d[t.first] + v[t.first][i].second;
w[v[t.first][i].first] = w[t.first];   //path cal
prev[v[t.first][i].first] = t.first;
Q.push(v[t.first][i]);
}
else  if(d[t.first] + v[t.first][i].second == d[v[t.first][i].first])
w[v[t.first][i].first] += w[t.first]; //path cal
}
}
}
int main()
{
//freopen("input.txt","r",stdin);
while(scanf("%d",&ver)==1 && ver)
{
for(int i=0;i<=ver;i++) v[i].clear();
scanf("%d",&edg);
for(int i=0;i<edg;i++)
{
scanf("%d%d%d",&e1,&e2,&wed);
v[e1-1].push_back(pa(e2-1,wed));
v[e2-1].push_back(pa(e1-1,wed));
}
dijkstra(0);
//_print(1);
cout<<w[1];
cout<<endl;
}
return 0;
}
``````

DD
Experienced poster
Posts: 145
Joined: Thu Aug 14, 2003 8:42 am
Location: Mountain View, California
Contact:

### Re: 10917 - A Walk Through the Forest

Anindya wrote:Oh that was fully because of a small mistake in the implementation of dijkstra.

Now got AC

Jan's first set of output should be like this:

Code: Select all

``````6 9
1 6 2995
6 3 4827
3 1 32391
3 5 12382
5 4 18716
4 3 19895
6 1 1869
1 5 25667
5 2 17035``````
Ouput is the same as given by him.
I think the input graph is a undirected graph such that this input test case may need some modifications since it contains (1, 6) and (6, 1).
Have you ever...
• Wanted to work at best companies?
• Struggled with interview problems that could be solved in 15 minutes?
• Wished you could study real-world problems?
If so, you need to read Elements of Programming Interviews.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 10917 - A Walk Through the Forest

I Tried many Test-cases compared with UVA toolkit's output and it passed all.
I counted path as sclo said and as aninnda implemented...could not figure out reason behind WA...please help anyone....here is my code

Code: Select all

``````
//Cut After Getting Accepted...

``````

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

### Re: 10917 - A Walk Through the Forest

here u must not use adjacency matrix for representaiom
use array of vectors because there can be more than one undirected edges bw two nodes
first run dijkstra sssp with STL heap and get distances from node 2
create dag using dist[a]>dist
in dag also u can have more than one edges between two nodes
NO NEED OF TOPOLOGICAL SORT
use dp for memorisation
here is my AC code
http://ideone.com/xIctc2

New poster
Posts: 1
Joined: Fri Mar 13, 2015 6:17 pm

### Re: 10917 - Walk Through the Forest

I have tried solving this problem but still getting WA but every testcase i try i get it correct on my PC

Code: Select all

``````#include<iostream>
#include<vector>
#include<queue>
#define MAX 1000000010
using namespace std;
struct akm{
int pou;
int pws;
};
long apos[1001]; //Distance Array
long epip[1001];
long mono[1001]; //Incoming Edges counter array
struct checki{
bool operator()(int a, int b)
{
return (apos[a]>apos[b]);
}
};
int n, m;
priority_queue<int, vector<int>, checki> sir;
vector<int>kani; //Topological Sort
queue<int>vapo; //Help for Topological sort
vector<akm>row;
vector< vector<akm> > lista(1001, row); //First adjacency list
vector<int>row2;
vector< vector<int> > xlist(1001, row2); //Second adjacency list
bool v[1001];
//Renew Function
void renew()
{
int i;
for(i=0; i<=n; i++)
{
lista[i].clear();
v[i]=false;
apos[i]=MAX;
epip[i]=0;
mono[i]=0;
drom[i]=0;
kani.clear();
xlist[i].clear();
}
}
void diav()
{
int i, x, y, z;
akm temp;
for(i=0; i<m; i++)
{
cin>>x>>y>>z;
temp.pou=y;
temp.pws=z;
lista[x].push_back(temp);

temp.pou=x;
lista[y].push_back(temp);

}
}
//Djikstra Algo
void dj()
{
int i;
apos[2]=0;
sir.push(2);
v[2]=true;
while(!sir.empty())
{
for(i=0; i<lista[sir.top()].size(); i++)
{
apos[lista[sir.top()][i].pou]=min(apos[lista[sir.top()][i].pou], apos[sir.top()]+lista[sir.top()][i].pws);
if(!v[lista[sir.top()][i].pou])
{
v[lista[sir.top()][i].pou]=true;
sir.push(lista[sir.top()][i].pou);
}
}
sir.pop();
}
}
//Creation of the new list
void newlist(int st)
{
v[st]=true;
int i;
for(i=0; i<lista[st].size(); i++)
{
if(apos[lista[st][i].pou]<apos[st])
{
xlist[st].push_back(lista[st][i].pou);

}
if(!v[lista[st][i].pou])
{
newlist(lista[st][i].pou);
}
}
}
//Creation of Topological Sort
void topsort()
{
int i;
for(i=1; i<=n; i++)
{
if(mono[i]==0)
vapo.push(i);
}
while(!vapo.empty())
{
kani.push_back(vapo.front());
for(i=0; i<xlist[vapo.front()].size(); i++)
{
mono[xlist[vapo.front()][i]]--;
if(mono[xlist[vapo.front()][i]]==0)
vapo.push(xlist[vapo.front()][i]);
}
vapo.pop();
}
}
int main()
{
int i, j;
cin>>n;
while(n!=0)
{
cin>>m;
renew();
diav();
dj();
for(i=0; i<=n; i++)
v[i]=false;
newlist(1);
//Counting Incoming Edges
for(i=1; i<=n; i++)
{
for(j=0; j<xlist[i].size(); j++)
{
mono[xlist[i][j]]++;
}
}

topsort();
drom[1]=1;
//DP time
for(i=0; i<n; i++)
{
for(j=0; j<xlist[kani[i]].size(); j++)
{
drom[xlist[kani[i]][j]]+=drom[kani[i]];
}
}
cout<<drom[2]<<"\n";
cin>>n;
}
}
``````
Thank you very very very much for your help