10917 - Walk Through the Forest

[shantanu18]

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]

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).

[Imti]

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]

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]

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