10000 - Longest Path

[renato_ferreira]

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]

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.

[renato_ferreira]

Thank you very much, AC!

[jj_99]

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]

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

[WingletE]

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;
                        }
                    }
                }
}


[WingletE]

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]

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

[hammerx]

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]

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;
}


[kbr_iut]

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;
}



[ashish_thakur]

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[i]=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]

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]

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

[Articuno]

You can use BFS to find the longest path. I used that and got AC.