10000 - Longest Paths

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

Moderator: Board moderators

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

Post by renato_ferreira » Mon Aug 13, 2007 9:14 pm

Can I say that if a vertex is on the queue, it don't need to go again?
Because I tried to do it, and got WA.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Aug 13, 2007 10:44 pm

Two things to change...

Code: Select all

void bfs(int s){ 
    ....

    set all d[i] to 0. // 1st part updated here

    while (!fila.empty()){ 
        ...
        
        for (v = 1; v <= n; v++){ 
            if (g[u][v] == 1 && d[v] < d[u]+1){ // 2nd part updated here 
                ....
            } 
        } 
    } 
} 
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

renato_ferreira
New poster
Posts: 21
Joined: Thu Jun 14, 2007 11:45 pm

Post by renato_ferreira » Tue Aug 14, 2007 1:09 am

Thank you very much, AC!

jj_99
New poster
Posts: 2
Joined: Fri Nov 23, 2007 7:48 pm

Post by jj_99 » Sat Jan 05, 2008 9:01 pm

i have try many input and the output is correct.
but also get WA
can u help me to check it,pls
thz...

Code: Select all

#include <stdio.h>
#include <stdlib.h>

int d[100][100];
int b[100];
int length;
int s;

int max(int a,int b)
{
    if (a>b)
       return a;
    return b;    
}

int intial(){
    int i,j;
    for(i=0;i<=100;i++){
    b[i]=-1;
        for(j=0;j<=100;j++)
            d[i][j]=0; 
    } 
}

void calculate(int k, int n){
    int i,j;
    
    if(b[k]==1)
    {
    for (i=n;i>=1;i--)
       if(d[k][i]!=0)
           d[s][i]=max(d[s][i],d[s][k]+d[k][i]);
    }
   
    if(b[k]==-1){
    for (i=n;i>=1;i--){
         if(d[k][i]==1)
         {
             d[s][i]=max(d[s][i],d[s][k]+d[k][i]);
               calculate(i,n);
               
               for (j=n;j>=1;j--)
                   if(d[i][j]!=0)
                       d[k][j]=max(d[k][j],d[k][i]+d[i][j]);
               
               b[k]=1;
             
         }        
       }
    }
    if(b[k]!=1){
                    
       b[k]=0;
       }
}

int main(){
    int t1,t2;
    int n,i,j;
    int finish;
    int count=0;
    
    while(scanf("%d",&n)==1 && n!=0)
    {
       count++;
       intial();
       length=0;
       scanf("%d",&s);    
       finish=s;            
       while(scanf("%d%d",&t1,&t2)==2 && t1!=0 && t2!=0){
           d[t1][t2]=1;                 
       }
       calculate(s,n);
       
       for(i=1;i<=n;i++){
           if(length<d[s][i]){
              length=d[s][i];
              finish=i;
            }
          }
          
       printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",count,s,length,finish);
    
    }      

}

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Sat Feb 23, 2008 8:55 pm

CHECK THIS INPUT OUTPUT:

Code: Select all

8
8
2 4
3 5
6 8
1 8
5 6
4 7
4 5
5 8
1 5
1 3
2 3
1 7
7 8
3 4
1 2
2 8
2 6
4 6
1 6
6 7
2 7
2 5
5 7
1 4
3 8
3 7
3 6
4 8
0 0
OUTPUT:
Case 9: The longest path from 8 has length 0, finishing at 8.
HOPE IT WORKS
''I want to be most laziest person in the world''

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Post by WingletE » Thu Feb 28, 2008 10:42 am

I tried to solve this problem using Floyd-Warshall but getting wrong.
I think there must be some logical mistake in my code, but I don't know where it is.

This is part of my code.
Somebody please give me some suggestion. Thank you!

Code: Select all

/*
1. M is zero.
2. In the beginning matrix[i][j] is set to 1 if i and j are connected, set to M otherwise.
3. Before calling this function, all the elements in v[][][] is initialized to false.
4. If the longest path from i to j has to go through k, v[i][j][k] is set to true.
*/
void longest_path(const int& size)
{
    for(int k = 0; k < size; k++)
        for(int i = 0; i < size; i++)
            for(int j = 0; j < size; j++)
                if((matrix[i][k] != M) && (matrix[k][j] != M) && (v[i][k][j] == false) && (v[j][k][i] == false) && (i != j) && (j != k) && (k != i))
                {
                    int temp = matrix[i][k] + matrix[k][j];
                    
                    if(matrix[i][j] < temp)
                    {
                        bool k = false;
                        
                        for(int q = 0; q < size; q++)
                            if((v[i][k][q] == true) && (v[k][j][q] == true))
                            {
                                k = true;
                                break;
                            }
                        
                        if(k == false)
                        {
                            matrix[i][j] = matrix[j][i] = temp;
                            
                            for(int q = 0; q < size; q++)
                                if((v[i][k][q] == true) || (v[k][j][q] == true))
                                    v[i][j][q] = v[j][i][q] = true;
                            
                            v[i][j][k] = v[j][i][k] = true;
                        }
                    }
                }
}

User avatar
WingletE
New poster
Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan
Contact:

Post by WingletE » Mon Mar 03, 2008 2:46 pm

Another question:
I've seen at somewhere that this problem can be solved using DFS, but how can I use DFS without getting TLE?

And could someone explain the ideas of other solutions for me?
I think there are many better solutions above, but I can't understand them very well.

Thanks.

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Fri Mar 14, 2008 2:07 pm

u can solve this easily by use flowyed warshel algorithm.
but u also solve this by DFS.
--U HAVE TO CHECK THE LAST NODE OF A PATH.
--SAVE THE LENGTH OF PATH & LAST NODE.
--NODE NEED RUN BY ALL THE NODE.
--START WITH SOURCE NODE.

ALL THE BEST
''I want to be most laziest person in the world''

hammerx
New poster
Posts: 1
Joined: Wed Feb 06, 2008 8:34 am

Re: 10000 - Longest Path

Post by hammerx » Mon May 12, 2008 8:32 am

any idea why runtime error? can't find any bug....thanks in advance

Code: Select all


#include<stdio.h>
#define max 110
int d[max],source,color[max],indeg[max],tsort[max],adj[max][max];
int n,k,used[max],white=10,grey=11,black=12;

void top_sort()
{
	int i,j,l;

	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(indeg[j]==0&&used[j]==0)
			{
				tsort[k++]=j;
				used[j]=1;
				for(l=1;l<=n;l++)
				{
					if(adj[j][l]==1)
					{
						indeg[l]--;
					}
				}
			
			}
		}
	
	}

	
}

void bfs()
{
	int i,j,temp,u,v,q[110],f,r,count=0;
	for(i=1;i<=n;i++)
	{
		color[i]=white;
		d[i]=0;
	}
	color[source]=grey;
	temp=source;
	f=1;
	r=1;
	q[f]=source;
	r++;
	while(r!=f)
	{
		
		u=q[f];
		f++;
		for(v=1;v<=n;v++)
		{
			if(adj[u][tsort[v]]==1)
			{
				if(color[tsort[v]]==white||d[u]>=d[tsort[v]])
				{
					color[tsort[v]]=grey;
					d[tsort[v]]=d[u]+1;
					q[r]=tsort[v];
					r++;
				}
			
			}
		
		}
	
		
	}



}
int main()
{
	int i,j,p,q,maxx=0,dest,c=0;
//	freopen("10000.txt","rt",stdin);
	while(scanf("%d",&n)==1)
	{
		if(n==0)
			break;
		
		scanf("%d",&source);
		
		for(i=1;i<=n;i++)
		{
			indeg[i]=0;
			used[i]=0;
			for(j=1;j<=n;j++)
			{
				adj[i][j]=0;
			
			}
		
		}
		
		while(scanf("%d %d",&p,&q)==2)
		{
			if(p==0&&q==0)
				break;
			adj[p][q]=1;
			indeg[q]++;
		
		}
		
		
		k=1;
		top_sort();	
		
		bfs();
		maxx=0;
		for(i=1;i<=n;i++)
		{
			
			if(d[i]>maxx)
			{
				maxx=d[i];
				dest=i;
			}
		
		}
		if(maxx==0)
			dest=source;
		printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",++c,source,maxx,dest);
	
	}

return 0;
}





MarioYC
New poster
Posts: 2
Joined: Thu Aug 07, 2008 2:54 am

Re: 10000 - Longest Path

Post by MarioYC » Thu Aug 07, 2008 3:00 am

Hi, I'm getting wrong answer with this code, could you tell me what's my mistake?

Code: Select all

#include<iostream>
#include<queue>
#include<map>

using namespace std;

int n,s;
int longest;
int destiny;
int visited[101];

vector< vector<int> > L(101);

void bfs(){
    queue< pair<int,int> > Q;
    Q.push(make_pair(s,0));
    
    pair<int,int> aux;
    
    while(!Q.empty()){
        aux=Q.front();
        Q.pop();
                
        if(aux.second>visited[aux.first]){
            visited[aux.first]=aux.second;
            
            if(aux.second>longest){
                longest=aux.second;
                destiny=aux.first;
            }else if(aux.second==longest && aux.first<destiny) destiny=aux.first;
            
            for(int i=0;i<L[aux.first].size();i++)
                Q.push(make_pair(L[aux.first][i],aux.second+1));
        }
    }
}

int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);

    int caso=1,p,q;

    while(1){
        scanf("%d",&n);
        if(n==0) break;
        
        scanf("%d",&s);
        
        for(int i=0;i<n;i++) L[i].clear();
        
        while(1){
            scanf("%d %d",&p,&q);
            if(p==0 && q==0) break;
            
            L[p].push_back(q);
        }
        
        destiny=s;
        longest=0;
        memset(visited,-1,sizeof(visited));
        
        bfs();
        
        cout<<"Case "<<caso<<": The longest path from "<<s<<" has length "<<longest<<", finishing at "<<destiny<<"."<<endl<<endl;
        caso++;
    }

    return 0;
}

User avatar
kbr_iut
Experienced poster
Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH
Contact:

Re: 10000 - Longest Path(15 time WA)

Post by kbr_iut » Fri Sep 12, 2008 10:25 pm

I have checked all of the inputs of this topic(all of 9 pages).but getting correct answer. i generate random numbers.although i got correct answer(checked at uvatoolkit)..still now i didnt get where is the bug.
i used floyed warshall and assumed
1. the graph is directed.
2.if source and destination is same then length is 0.
3.repeatedly checked code and submited.but in vain.....
pliz who have solved,,,,help.here is my code.

Code: Select all

#include<iostream>
#include<algorithm>
using namespace std;
#define mx 210
#define inf 32767
int m[mx][mx],mm[mx][mx],path[mx][mx],n,u,v,t;
void floyed(){
	int i,j,k;
	for(k=1;k<=n;k++)
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				if(m[i][k]!=inf&&m[k][j]!=inf){
					m[i][j]=m[i][k]+m[k][j],mm[i][j]=mm[i][k]+mm[k][j],path[i][j]=path[i][k];
				}
}
int main(){
	int i,j,kk=0;
	//freopen("1.txt","r",stdin);
	while(cin>>n>>u&&n){
		fill(m[0],m[n+1],inf);
		fill(mm[0],mm[n+1],0);
		while(cin>>i>>j&&(i||j)){
			m[i][j]=1;
			mm[i][j]=1;
		}
		floyed();
		v=0;
		int I=u;
		for(i=1;i<=n;i++){
			if(i==u)continue;
			if(v<mm[u][i])v=mm[u][i],I=i;
		}
		cout<<"Case "<<++t<<": The longest path from "<<u<<" has length "<<v<<", finishing at "<<I<<".\n\n";
	}
	return 0;
}

It is tough to become a good programmer.
It is more tough to become a good person.
I am trying both...............................

ashish_thakur
New poster
Posts: 7
Joined: Mon Dec 22, 2008 3:00 pm

Re: 10000 - Longest Path

Post by ashish_thakur » Wed Dec 24, 2008 1:01 am

I am getting Runtime error please help

#include<stdio.h>
#include<stdlib.h>

struct node{
int value;
struct node * next;
};

int numNodes;
int largestDepth;

VISIT(struct node **Node, int n){
static int depth=0;
struct node *NODE = Node[n];
while(NODE!=0){
++depth;
VISIT(Node,NODE->value);
NODE=NODE->next;
}
if(depth>largestDepth)
largestDepth=depth;
depth=0;

}

int main(void){

int caseNo=1;
while(1){
int startNode;
scanf("%d",&numNodes);

if(numNodes<1)break;
scanf("%d",&startNode);
struct node *Node[numNodes+1];
int i;
for(i=1;i<numNodes+1;i++){
Node=0;
}
int p,q;

while(1){
scanf("%d",&p);
scanf("%d",&q);
if(p==0 && q==0)
break;

if(Node[p]==0){
Node[p] = (struct node *)malloc(sizeof (struct node));
Node[p]->value=q;
Node[p]->next=0;
}else{
struct node * head=Node[p];
while(head->next!=0){
head=head->next;
}

struct node * new= (struct node *)malloc(sizeof (struct node));
new->value=q;
new->next=head;
head->next=new;
new->next=0;
}
}

VISIT(Node,startNode);
printf("Case %d: The longest path from %d has length %d finishing at %d.\n",caseNo,startNode, largestDepth,2); // yet to implement smallest node among the same longest length using 2 here
largestDepth=0;
caseNo++;
}
}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10000 - Longest Path

Post by mf » Wed Dec 24, 2008 1:50 am

Use [code]...[/code] to post code.

If you submit your program as C, one of the reasons of a runtime error verdict can be a non-zero exit code. Make sure that your main() returns 0.

Also, it seems like you're missing commas in the output, and don't print newlines between outputs for different cases. You'd get WA for that - judge expects your program's output to be byte-wise equal to a reference solution's output.

ashish_thakur
New poster
Posts: 7
Joined: Mon Dec 22, 2008 3:00 pm

Re: 10000 - Longest Path

Post by ashish_thakur » Wed Dec 24, 2008 11:30 am

Thanks , Now I am getting TL error is there any standard algo for this type of problem

Articuno
Learning poster
Posts: 78
Joined: Sun Nov 30, 2008 5:00 pm
Location: IUT-OIC, Dhaka, Bangladesh

Re: 10000 - Longest Path

Post by Articuno » Wed Dec 24, 2008 11:49 am

You can use BFS to find the longest path. I used that and got AC.
May be tomorrow is a better day............ :)

Post Reply

Return to “Volume 100 (10000-10099)”