10917 - Walk Through the Forest

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

Re: 10917 - A Walk Through the Forest

Post by shantanu18 » Fri Aug 06, 2010 8:46 am

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

Post by DD » Mon Mar 28, 2011 6:04 am

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

Now got AC :D

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
Location: Bangladesh
Contact:

Re: 10917 - A Walk Through the Forest

Post by Imti » Sat Sep 03, 2011 1:03 pm

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

Post by prashantharshi » Wed Jun 18, 2014 8:16 am

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

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

Re: 10917 - Walk Through the Forest

Post by adamos2468 » Fri Mar 13, 2015 6:27 pm

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
long drom[1001]; //Roads Counter
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();
    }
}
//Reading Function
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 :)

Post Reply

Return to “Volume 109 (10900-10999)”