## 10099 - The Tourist Guide

Moderator: Board moderators

Grazyna
New poster
Posts: 16
Joined: Wed Apr 20, 2005 2:44 pm
Location: Thessaloniki,Greece
Hi.
it seems that I have an unsolvable problem with 10099.
The algorithm seems simple but I'm receiving WA continously.
Can someone take a look at my code?

Code: Select all

``````thanks for anybody who tried.
``````
Thanks in advance for any suggestion,
grazyna

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka

### Did not understand

I've understood that it is a mximin Floyed warshal but in the prob. pic 1-2-4-7 will take 25 passenger but why 5 trip whereas 4 trip....

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
I am not totally remembering the problem.
But did you consider that the guide will be between the persons that will travel. i mean if 25 person is traveling, then they are 1(guide)+24(others)
Sleep enough after death, it is the time to work.

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka
Thnx for help but yet i got WA plz check my code here.......

Code: Select all

``````Removed
``````
Plz help;;;;;;;;;;;;;;;;;;
Last edited by rhsumon on Thu Jun 28, 2007 2:18 pm, edited 1 time in total.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:
I do not know, but i think problems in initialization. I think ur init() will copy old values from test cases.

I think u must intialize array with zeros, then read & set input in it. Ur code seem to be right
Sleep enough after death, it is the time to work.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Use

Code: Select all

``printf("Scenario #%d\n",c);``
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

rhsumon
New poster
Posts: 48
Joined: Wed Aug 23, 2006 12:29 pm
Location: Dhaka
Thank u jaan .......... it's a silly mistake
Now i got AC
thnx again

Thnks also to 898989 vai

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:
Ami ekhono shopno dekhi...
HomePage

N@\$!M
New poster
Posts: 10
Joined: Wed Jan 10, 2007 7:26 pm
What is wrong with my code ?

Code: Select all

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

#define num 105

long w[num][num], cost;

long min(long a,long b) { return ( (a<b) ? a : b ) ; }

long max(long a,long b) { return ( (a>b) ? a : b ) ; }

void MaxMinWarshall(long n)
{
long i,j,k;

for (k=1; k<=n; k++)
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
w[j][i] = w[i][j] = max(w[i][j], min(w[i][k], w[k][j]));
}

int main(void)
{
long i,j,n,in , test_case = 0  ;
long N,R,  a,b,cost   ,from,to,p;

while(scanf("%ld%ld",&N,&R)==2)
{
if(N==0 && R==0) break;

printf("Scenario #%ld\n",++test_case);
for(i=1;i<=num;i++)
{
for(j=i;j<=num;j++)
{
w[j][i] = w[i][j] = 0 ;
}
}

for(i=1;i<=R;i++)
{
scanf("%ld%ld%ld",&from,&to,&cost);
w[to][from] = w[from][to] = cost;
}

MaxMinWarshall(N);

scanf("%ld%ld%ld",&from,&to,&p);

printf("%ld\n\n",(long) ceil(p*1.0 / (w[from][to]-1) ) );

}
return 0;
}

``````
"I AM NOT SURE WHETHER I SHOULD BE CONFUSED OR NOT..."
TARIQ M NASIM
CSE 03/04 Batch, SUST, Sylhet- 3114.
==>Software Engineer, Structured Data Systems Limited,Dhaka.

tariqmnasim@gmail.com

willima
New poster
Posts: 13
Joined: Wed Dec 07, 2005 1:19 pm
Location: Brazil

### I'll tell what's really wrong...

Hi.

After getting many and many WA in this problem, I discovered that I had just to add a second blank line at the final of output. Doing this I finally got AC, just because one BLANK LINE at the end!!!

So, for those who are trying this problem, pay attention to this!!

Regards.
"Don't let the day go by
Don't let it end
Don't let the day go by, in doubts
The anwser lis within"

yjwoo14
New poster
Posts: 7
Joined: Wed Jan 09, 2008 5:58 am

### I don`t know wrong in my code

This is Floyd Version Code . This code return WA

Code: Select all

`````` cut after AC..,
``````
This is BFS Version.. This code return TLE

Code: Select all

``````#include <iostream>
#include <vector>
#include <queue>

#define min(x, y) (x<y)?x:y
#define MAXN 101

using namespace std;

struct node {
int first;
int second;
bool path[MAXN];
};

bool operator < (node a, node b){
return a.first < b.first;
}

vector<pair<int,int> > V[MAXN];

int main(){
int n, r, scnt = 1;

while(1){
cin >> n >> r;

if (!n && !r)
break;

int f, t, w, start, end, tot;
pair<int, int> temp;

for (int i = 0 ; i < r ; i++){
cin >> f >> t >> w;
temp.first = w;
temp.second = t;
V[f].push_back(temp);
temp.second = f;
V[t].push_back(temp);
}

cin >> start >> end >> tot;

priority_queue<node > PQ;

node tp, ip;

for (int i = 0 ; i < V[start].size() ; i++){
memset(&ip, 0, sizeof(node));
ip.first = V[start][i].first;
ip.second = V[start][i].second;
ip.path[ip.second] = true;
ip.path[start] = true;
PQ.push(ip);
}

int max = 0;

while(!PQ.empty()){
tp = PQ.top();

PQ.pop();

if (max > tp.first)
break;
if (tp.second == end && tp.first > max)
max = tp.first;
for (int i = 0 ; i < V[tp.second].size() ; i++){
if (tp.path[V[tp.second][i].second])
continue;
ip.first = min(tp.first, V[tp.second][i].first);
ip.second = V[tp.second][i].second;
memcpy(ip.path, tp.path, sizeof(bool) * n);
ip.path[ip.second] = true;
PQ.push(ip);
}
}
int result = 0;

while (tot > 0){
tot -= (max - 1);
result++;
}
cout << "Scenario #" << scnt++ << endl << "Minimum Number of Trips = ";
cout << result << endl << endl;
}
}
``````
I don`t know.. what`s wrong? Plz Help me
Last edited by yjwoo14 on Mon Jan 14, 2008 12:40 pm, edited 1 time in total.

slxst
New poster
Posts: 23
Joined: Mon Oct 16, 2006 2:18 am

### Re: I don`t know wrong in my code

yjwoo14 wrote:I don`t know.. what`s wrong? Plz Help me
I'm using the same idea but also get WA. At first I thought that your error was really a PE because of:
yjwoo14 wrote: cout << "Minimum Number of Trips = " << result << endl << endl;
But it still got WA.

My code is:

Code: Select all

``````#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <cmath>
#include <climits>
using namespace std;

int travel(vector< vector<int> >& matrix, int origin, int destination)
{
queue<int> myQueue;
myQueue.push(origin);
int s = matrix.size();

vector<int> passengers(s, -1);
vector<bool> visited(s, false);

passengers[origin] = INT_MAX;

while(!myQueue.empty())
{
int node = myQueue.front();
myQueue.pop();

visited[node] = true;

for(int i=0; i<s; ++i)
{
if(matrix[node][i]>0)
{
if(!visited[i])
myQueue.push(i);
passengers[i] = max(passengers[i], min(passengers[node], matrix[node][i]));
}
}
}

return passengers[destination];
}

int main(int argc, char** argv)
{
int n=1, nodes, edges;
cin >> nodes >> edges;
while(nodes!=0)
{
vector< vector<int> > matrix(nodes, vector<int>(nodes,-1));

for(int times=1; times<=edges; ++times)
{
int x, y, weight;
cin >> x >> y >> weight;
matrix[x-1][y-1] = matrix[y-1][x-1] = weight;
}

int origin, destination, passengers;
cin >> origin >> destination >> passengers;

int m = travel(matrix, origin-1, destination-1);

if(n>1)
cout << endl;

cout << "Scenario #" << n++ << endl
<< "Minimum Number of Trips = " << (int)(ceil(passengers/(m-1.0))) << endl;

cin >> nodes >> edges;
}
return 0;
}
``````
[/quote]

yjwoo14
New poster
Posts: 7
Joined: Wed Jan 09, 2008 5:58 am

### I`ve Solved

.. Because of Initialize..

That is 2-th Array;;;;;

Couldn`t Initialize memset

turcse143
Learning poster
Posts: 81
Joined: Wed May 09, 2007 9:59 pm
check this input:

Code: Select all

``````input:
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 1 99
0 0
output:
Scenario #1
Minimum Number of Trips = 0
``````
hope it helps.
''I want to be most laziest person in the world''

x140l31
Learning poster
Posts: 69
Joined: Tue Jan 30, 2007 12:51 am

### Re: 10099 - The Tourist Guide

anyone can see what's wrong in this code?

Code: Select all

``````#include <iostream>
#include <cmath>
using namespace std;

int main()
{
int n, r, sce = 1;
while (cin >> n >> r and n)
{
int minRoads[n + 1][n + 1], x, y, t;
for (int j = 1; j <= n; ++j)
for (int i = 1; i < j; ++i) minRoads[i][j] = 0;
while (r--)
{
scanf("%d %d %d", &x, &y, &t);
if (x > y) swap(x, y);
}

for (int k = 1; k <= n; ++k)
for (int i = 1; i < k; ++i)
for (int j = k + 1; j <= n; ++j)