10000 - Longest Path

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

Moderator: Board moderators

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.
renato_ferreira
New poster

Posts: 21
Joined: Thu Jun 14, 2007 11:45 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
Jan
Guru

Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm

Thank you very much, AC!
renato_ferreira
New poster

Posts: 21
Joined: Thu Jun 14, 2007 11:45 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);        }      }`
jj_99
New poster

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

CHECK THIS INPUT OUTPUT:
Code: Select all
`882 43 56 81 85 64 74 55 81 51 32 31 77 83 41 22 82 64 61 66 72 72 55 71 43 83 73 64 80 0OUTPUT: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''
turcse143
Learning poster

Posts: 81
Joined: Wed May 09, 2007 9:59 pm

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
New poster

Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan

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.

WingletE
New poster

Posts: 35
Joined: Sun Aug 13, 2006 1:34 pm
Location: Taipei, Taiwan

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.

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

Posts: 81
Joined: Wed May 09, 2007 9:59 pm

Re: 10000 - Longest Path

any idea why runtime error? can't find any bug....thanks in advance
Code: Select all
`#include<stdio.h>#define max 110int 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;}`
hammerx
New poster

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

Re: 10000 - Longest Path

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;}`
MarioYC
New poster

Posts: 2
Joined: Thu Aug 07, 2008 2:54 am

Re: 10000 - Longest Path(15 time WA)

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 32767int 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...............................

kbr_iut
Experienced poster

Posts: 103
Joined: Tue Mar 25, 2008 11:00 pm
Location: IUT-OIC, DHAKA, BANGLADESH

Re: 10000 - Longest Path

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

struct node * new= (struct node *)malloc(sizeof (struct node));
new->value=q;
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++;
}
}
ashish_thakur
New poster

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

Re: 10000 - Longest Path

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.
mf
Guru

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

Re: 10000 - Longest Path

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

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

Re: 10000 - Longest Path

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

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

PreviousNext