UVA – 10000 – Longest Paths   2 comments


solved using dfs + memo
#include <stdio.h>
char map[200][200];
int dp[200][200];
int max(int a,int b)
{
	return(a>b)?a:b;
}
int length(int s,int t,int n)
{
	if(dp[s][t]!=-1)
		return dp[s][t];
	else
	{
		int maximum = -1;
		int i;
		for(i=1;i<=n;i++)
			if(map[s][i])
				maximum = max(maximum,1+length(i,t,n));
		return dp[s][t]=maximum;
	}
}
int main()
{
	int n,a,b,i,s,j,best,m,c;
	c = 1;
	scanf("%d",&n);
	while(n)
	{
		scanf("%d",&s);
		for(i=0;i<=n;i++)
		{
			for(j=0;j<=n;j++)
			{
				map[i][j]=0;
				dp[i][j]=-1;
			}
			dp[i][i]=0;
		}
		scanf("%d %d",&a,&b);
		while(a||b)
		{
			map[a][b]=1;
			scanf("%d %d",&a,&b);
		}
		m = -1;
		best = 0;
		for(i=1;i<=n;i++)
			if(length(s,i,n)>m)
			{
				m = length(s,i,n);
				best = i;
			}
		printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",c++,s,m,best);
		scanf("%d",&n);
	}
	return 0;
}
Advertisements

Posted August 17, 2011 by epicrado in DAG

2 responses to “UVA – 10000 – Longest Paths

Subscribe to comments with RSS.

  1. hey , anyone please help me in understanding this code.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: