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

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Sat Mar 23, 2002 12:10 pm

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
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

Post by PMNOX » Sat Mar 23, 2002 1:37 pm

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
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Sat Mar 23, 2002 1:48 pm

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
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

Post by PMNOX » Sat Mar 23, 2002 1:52 pm

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

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:

Post by Stefan Pochmann » Sat Mar 23, 2002 2:02 pm

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
Experienced poster
Posts: 169
Joined: Wed Oct 31, 2001 2:00 am
Location: Singapore

Post by junjieliang » Sat Mar 23, 2002 5:03 pm

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.:smile:

PMNOX
New poster
Posts: 49
Joined: Wed Feb 13, 2002 2:00 am
Location: Poland
Contact:

Post by PMNOX » Sat Mar 23, 2002 8:09 pm

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

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

10000 WA

Post by Larry » Tue Jul 09, 2002 10:39 am

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
Learning poster
Posts: 96
Joined: Mon Jun 24, 2002 1:22 pm
Location: Hungary
Contact:

Post by Picard » Tue Jul 09, 2002 1:46 pm

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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Wed Jul 10, 2002 12:26 am

Thanks. I'm soo careless nowadays.

ngochp
New poster
Posts: 1
Joined: Thu Sep 12, 2002 7:09 pm
Location: Singapore
Contact:

10000 - Longest Path

Post by ngochp » Thu Sep 12, 2002 7:14 pm

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
New poster
Posts: 14
Joined: Tue Jun 25, 2002 8:50 am

Post by tenshi » Tue Sep 17, 2002 1:11 pm

what the answer if source and destination is the same ?
http://www.ioiforum.org/en/

A problem discussing forum.
Welcome to discuss problems in it!

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Mon Jan 20, 2003 2:55 pm

you can use Warshall algorithm.

b3yours3lf
New poster
Posts: 44
Joined: Wed Aug 14, 2002 3:02 am

Post by b3yours3lf » Tue Sep 09, 2003 5:55 am

could someone give me input and output sample???

Thanks before.

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Sat Dec 06, 2003 8:03 am

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

(Late reply :) )
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Post Reply

Return to “Volume 100 (10000-10099)”