10099 - The Tourist Guide

[jambon_vn]

Hi,

According to this problem, you will use the route 1 - 2 - 4 - 7. And the maximum number of passengers is 25. But only 24 tourists can go each time because the tourist guide has to ride the bus with each group. The input sample has 99 tourists. With 4 trips only 96 tourists can go to the destination. So the output is 5 trips.

Is it clear enough for you?

[backbencher]

thanx

[efr_shovo]

/*Here Is My Code. Please Help*/

#include<stdio.h>


long n,R,C1,C2,P,W[100][100],s,d,t;

long min(long x,long y)
{
long mi;
if(x<y)
mi=x;
else
mi=y;
return mi;
}

long max(long x,long y)
{
long mx;
if(x>y)
mx=x;
else
mx=y;
return mx;
}


void F_W()
{
long k,i,j;
for(k=1;k<=n;k++)
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
W[j]=max(W[j],min(W[k],W[k][j]));
}

void main()
{
long i,j,mod,count=0,div=0,mutex=0;
freopen("c:\\in.txt","r",stdin);
while(1)
{
scanf("%ld %ld",&n,&R);
if(n<=0&&R<=0)
break;
else if(count)
printf("\n\n");
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
W[j]=0;
for(i=1;i<=R;i++)
{
scanf("%ld %ld %ld",&C1,&C2,&P);
if((C1<1&&C1>n)||C2<1&&C2>n||P<1)
{
mutex=1;
break;
}
W[C1][C2]=P;
W[C2][C1]=P;
}
if(mutex)
break;
F_W();
scanf("%ld %ld %ld",&s,&d,&t);
mod=t%(W[s][d]-1);
div=t/(W[s][d]-1);
if(count!=0)
printf("\n");
printf("Scenario #%ld\n",++count);
if(mod==0)
printf("Minimum Number of Trips = %ld\n",div);
else
printf("Minimum Number of Trips = %ld\n",++div);
}
}

[eg_frx]

Did you print a blank line after each scenario?

[Niaz]

There will be a complete blank line after each scenario. I am giving here a sample input output format. Hope it will help you.

Sample Input

Code: Select all

7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 7 99
0 0

Sample Output

Code: Select all

Scenario #1
Minimum Number of Trips = 5

Scenario #2
Minimum Number of Trips = 5
 <<------- [There is a new line also]

[neowarez]

Hi to all!!!

I am trying to solve this graph problem but it gives me TLE..

I use this metoth to find the MAX..

Code: Select all

void bfs(long a, long b, long cost) {
  long i;

  visitado[a]=1;
  if (a==b && cost>max)
    max=cost;
  else {
    for (i=0;i<=n;i++)
      if (!visitado[i] && edges[a][i]>0 && min(edges[a][i], cost)>max)
	bfs(i, b, min(edges[a][i], cost));
  }
  visitado[a]=0;
}

Is a better way to do it??

Thanks.

[neowarez]

No problem..

I already do it using MAXMIN floyds.

[ayon]

Hi,
my problem is very simple. I cannot undersatnd the sample input !!! In the sample input i think the maximin distance is 25. so for 99 tourists it takes minimum ceil(99/25) = 4 trips. then why they says Minimum Number of Trips = 5 ? plz help...

[mf]

Mr.G. counts as a passenger in each trip.

[ayon]

what a fool i am !!! anyway, thanx to mf very much, i wrote my code and got accepted

[Amran]

i can't understand why this code is runtime error.
can any one say why?


#include <stdio.h>
#include <math.h>

#define MAX 102
#define NEGINF -10000

#define max(a, b) ( (a > b) ? (a) : (b) )
#define min(a, b) ( (a < b) ? (a) : (b) )

long passengers[MAX][MAX];

void init( long roads ) {
long i, j;
for( i = 1; i <= roads; ++i )
for( j = 1; j <= roads; ++j )
passengers[i][j] = NEGINF;
}
int main()
{
long cities, roads, road1, road2;
long i, j, k, scinario = 0;
long source, des, totalPassengers;
scanf( "%ld%ld", &cities, &roads );
while( cities && roads )
{
init( roads );
for( i = 0; i < roads; ++i ){
scanf( "%ld%ld", &road1, &road2 );
scanf( "%ld", &passengers[road1][road2] );
passengers[road2][road1] = passengers[road1][road2];
}
scanf( "%ld%ld%ld", &source, &des, &totalPassengers );
for( k = 1; k <= cities; ++k )
for( i = 1; i <= cities; ++i )
for( j = 1; j <= cities; ++j )
passengers[i][j] = max( passengers[i][j], min( passengers[i][k], passengers[k][j]));

printf( "Scenario #%ld\nMinimum Number of Trips = %.0lf\n\n", ++scinario,
ceil( double(totalPassengers) / ( passengers[source][des] - 1 )));

scanf( "%ld%ld", &cities, &roads );
}
return 0;
}

[898989]

Salamo Aleko
Just in the intialization function

Mostafa Saad Wrote....
void init( int roads ) {
int i, j;
for( i = 1; i < MAX; ++i )
for( j = 1; j < MAX; ++j )
passengers[j] = 0;
}

[Amran]

Thanks, Mostafa Saad
At last i got accepted.

[beloni]

hello, my code was WA, whats wrong???

Code: Select all

I've solved that!		

thanks

[beloni]

so...
can you tell me some tip to get AC ?