10000 - Longest Paths

[Stefan Pochmann]

General advice: please indent your code for better readability. See FAQ how to do it.

And why do you post your program again? Ok, I see. That's your accepted version (at least I just got it accepted).

Mistake 1: You shouldn't flood this board with correct solutions. At least that's my personal opinion.

Mistake 2: You should've mentioned that you got it accepted, so that everybody knows what's going on.


<font size=-1>[ This Message was edited by: Stefan Pochmann on 2002-03-23 11:17 ]</font>

[PMNOX]

no, it's still wrong
i get just wrong answer

<font size=-1>[ This Message was edited by: PMNOX on 2002-03-23 12:43 ]</font>

[Stefan Pochmann]

Well, as I said, I just got it accepted. So get yourself a real mail client. You're probably using some M$-stuff, right? Some mail programs for example break lines when they shouldn't, so try to shorten your lines, max 60 or 70 characters. Or... get yourself a real mail client.

[PMNOX]

can u tell me which mail client should i use?
and where can i find faq, i couldn't find anyone

[Stefan Pochmann]

Depends on your operating system. If you have anything else than Unix, I can't help you, sorry... I always use the command line "mail", like
"mail judge@uva.es < prog.cpp". Could you look at the "We've got your program" response mail and look if that's the same program you sent? Or could you forward it to me (pochmann(AT)gmx.de)?

You can find the FAQ by clicking on "FAQ" in the upper right part of this window.

<font size=-1>[ This Message was edited by: Stefan Pochmann on 2002-03-23 13:07 ]</font>

[junjieliang]

How about using Hotmail? I use hotmail and it works well. Just make sure you're sending it as text format, not html.

Wish you good luck.

[PMNOX]

ok, i have change a few opcions in microsoft expess, so it works.

[Larry]

I don't know why this gives me WA. Thanks.

Code: Select all

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

int m = 0, t = 0, s;

boo( int go, int a[110][110], int b[110], int p ){
  int i;
  printf("%d %d\n", go, p );
  if ( p > m ) { m = p; t = go; }
  if ( p == m && t < go ) { t = go; }
  for ( i = 0; i < s; i++ ){
    if ( b[i] == 0 && a[go][i] ){
      b[i]++;
      boo( i, a, b, p + 1 );
      b[i]--;
    }
  }
}

int main(){
  int n, go, x, y, i;
  int a[110][110];
  int b[110];

  i = 1;
  while ( 1 == scanf("%d", &n ) && n){
    memset( a, 0, 110 * 110 * sizeof(int) );
    memset( b, 0, 110 * sizeof( int ) );
    scanf("%d", &go );
    t = go;
    s = n;
    m = 0;

    while ( 2 == ( scanf("%d %d", &x, &y ) ) ){
      if ( x == 0 && y == 0 ) break;
      a[x-1][y-1] = 1;
    }

    b[go-1] = 2;
    boo( go-1, a, b, 0 );
    printf("Case %d: The longest path from %d has length %d, finishing at %d.\n", i++, go, m, t + 1 );
  }
}

[Picard]

if there are several paths of maximum length you print the final place with largest number but you should print the smallest.

btw you left a printf in boo() and you should print a blank line after each solution. a 'void' return type for boo() and a 'return 0;' at the end of main() wouldn't hurt either.

[Larry]

Thanks. I'm soo careless nowadays.

[ngochp]

My code has wrong answer. Anybody can help me?
[cpp]
#include <iostream.h>
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include <memory.h>

const int max = 101;
/*---------------------------------------*/
int n, start, best, mem, ncase;
int ply[max];
short a[max][max];
/*---------------------------------------*/
void init(void)
{
memset(a, 0, sizeof(a));
memset(ply, 0, sizeof(ply));
}
/*---------------------------------------*/
void nhap(void)
{
int x, y;
scanf("%d", &n);
if (n > 0)
{
scanf("%d", &start);
memset(a, 0, sizeof(a));
do {
scanf("%d %d", &x, &y);
a[x][y] = 1;
} while ((x != 0) && (y != 0));
}
}
/*---------------------------------------*/
void init_ply(void)
{
int i;
for (i = 1; i <= n; i++)
ply = -1;
ply[start] = 0;
}
/*---------------------------------------*/
void process(void)
{
int i, j;
int stop = 0;
while (!stop)
{
stop = 1;
for (i = 1; i <= n; i++)
if (ply != -1)
for (j = 1; j <= n; j++)
if (a[j] == 1)
if (ply[j] < (ply + 1))
{
ply[j] = ply + 1;
stop = 0;
}
}
}
/*---------------------------------------*/
void cal_best()
{
int i;
mem = start;
best = 0;
for (i = 1; i <= n; i++)
if ((ply > best) || ((ply == best) && (i < mem)) )
{
best = ply;
mem = i;
}
}
/*---------------------------------------*/
void inkq()
{
printf("Case %d: The longest path from %d has length %d, finishing at %d.\n\n",
++ncase, start, best, mem);
}
/*---------------------------------------*/
main(void)
{
ncase = 0;
while (1)
{
init();
nhap();
if (n == 0) break;
init_ply();
process();
cal_best();
inkq();
}
return 0;
}
[/cpp]

[tenshi]

what the answer if source and destination is the same ?

[hank]

you can use Warshall algorithm.

[b3yours3lf]

could someone give me input and output sample???

Thanks before.

[Observer]

If you want to hv a high ranking in this problem, try implementing BFS!

(Late reply )