## 10099 - The Tourist Guide

Moderator: Board moderators

data_br
New poster
Posts: 1
Joined: Sat Aug 08, 2009 4:05 pm

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

Thanks willima, I had the same problem and this type of error makes me mad. Then finally I got Accepted

sajnt
New poster
Posts: 2
Joined: Fri Jun 18, 2010 10:03 pm

### Re: 10099 - The Tourist Guide

Hmm I used binary search together with DFS and got ElogE complexity.

rein08
New poster
Posts: 3
Joined: Mon Jul 19, 2010 2:25 pm

### Re: 10099 - The Tourist Guide

I'm new in this.
Im learning a lot.
Thanks.

valkov
New poster
Posts: 20
Joined: Tue Jul 20, 2010 3:11 pm

### Re: 10099 - The Tourist Guide

Just got AC on this problem. Here are some thoughts:
1. After each scenario you should output one empty line!
2. It might be a good idea if you check startPoint == endPoint 3. If you don't care much about the speed use Floyd's All-pairs shortest path algorithm and use long for all your variables
4. After executing the Floyd algorithm use the following:

Code: Select all

``````long touristsPerTrip = graph[start][end];
long trips = touristCount / touristsPerTrip;
if(touristCount % touristsPerTrip != 0) {
trips++;
}
``````
If you have any questions P.M. me P.S. D*mn it feels good to solve this problem jenovano2sko
New poster
Posts: 5
Joined: Tue Oct 19, 2010 8:07 am

### Re: 10099 - The Tourist Guide

Would anybody be so kind as to tell me where my code starts setting things to zero? I have identified that the line of code causing me to repeatedly get Runtime Error is the following:

Code: Select all

``````numTrips = numTourists / maxPossibleBandwidth;
``````
I'm using a modified Floy-Warshall/Roy-Floyd/WFI algorithm (our favorite n^3 all pairs shortest path). I initialize everything to LONG_MAX except for a single node to start filling in the array, and since the throughput between two nodes must always be greater than 1, I'm not sure how my throughput is ever reduced to zero. If you have any suggestions, please let me know.

Thanks a bunch!

Code: Select all

``````#include <iostream>
#include <climits>
#include <cstdlib>
#include <list>
using namespace std;

// edge[i] = k
// i is the node it is connected to
// k is the bandwidth of that edge
class Node {
public:
int edges;
};

class Edge {
public:
int toNode;
int bandwidth;
};

void clearNodes(Node *nodes);
void clearTable(int bandwidthTable[]);

int main(void)
{
Node nodes; //the array of nodes of our adjacency list
int bandwidthTable; //the table of bandwidths for our algorithm
Edge edges; //edges used for finding maximum bandwidth

int numCities,    // number of nodes in the graph
numEdges,     // number of edges in the graph
currNode1,    // first node scanned in
currNode2,    // second node scanned in
currBandwidth, // bandwidth between currNode1 and currNode2
sourceNode,   // the number of our source node
destNode,     // the number of our destination node
numTourists,  // the number of tourists to be taken on this trip
numTrips, //the number of trips it will take...
maxPossibleBandwidth; //the maximum possible bandwidth

cin >> numCities >> numEdges;

int caseNum = 1;
while(numCities != 0 || numEdges != 0) //outermost loop: for each case
{
if(numCities == 0 || numEdges == 0)
{
numTrips = 0;
goto myContinue;
}
//graph input:
clearNodes(nodes);
clearTable(bandwidthTable);
for(int i = 0; i < numEdges; i++)
{
cin >> currNode1 >> currNode2 >> currBandwidth;
currBandwidth--;
nodes[currNode1].edges[currNode2] = currBandwidth;
nodes[currNode2].edges[currNode1] = currBandwidth;
}
//obtain the source node and the destination node
cin >> sourceNode >> destNode >> numTourists;
if(sourceNode == destNode)
{
numTrips = 0;
goto myContinue;
}
//set up the table
bandwidthTable[destNode]--;
//compute the bandwidth table
int l;

for(int i = 1; i < numCities; i++) //for each number of edges 1 to n-1
{
for(int j = 1; j <= numCities; j++) //for each node 1 to n
{
l = 0;
for(int k = 1; k <= numCities; k++) //for each possible edge going from 1 to n
{
//if the edge exists
if( (nodes[j].edges[k] != 0) && (bandwidthTable[k][i-1] < LONG_MAX))
{
edges[l].toNode = k;
edges[l].bandwidth = min(nodes[j].edges[k], bandwidthTable[k][i - 1]);
l++;
}
} //for each possible edge going from 1 to n
//make the entry in the table
if(l)
{
int currMaxBandwidth = 0;
for(int m = 0; m < l; m++)
currMaxBandwidth = max(currMaxBandwidth, edges[m].bandwidth);
bandwidthTable[j][i] = currMaxBandwidth;
}
} //for each node 1 to n
}//for each number of edges 0 to n-1

//you now have your table complete.
maxPossibleBandwidth = 0;
for(int i = 1; i < numCities; i++)
if(bandwidthTable[sourceNode][i] < LONG_MAX)
maxPossibleBandwidth = max(maxPossibleBandwidth, bandwidthTable[sourceNode][i]);

numTrips = numTourists / maxPossibleBandwidth;
if(numTourists % maxPossibleBandwidth > 0)
numTrips++;

myContinue:
cout << "Scenario #" << caseNum << '\n' << "Minimum Number of Trips = " << numTrips << "\n\n";
//ends with:
caseNum++;
cin >> numCities >> numEdges;
} //outermost loop: for each case
return 0;
}

//all used edge bandwidths are greater than 0, so we can clear out the
//bandwidths between each test case by resetting them to zero.
void clearNodes(Node *nodes)
{
for(int i = 0; i < 101; i++)
for(int j = 0; j < 101; j++)
nodes[i].edges[j] = 0;
}

void clearTable(int bandwidthTable[])
{
for(int i = 0; i < 101; i++)
for(int j = 0; j < 101; j++)
bandwidthTable[i][j] = LONG_MAX;
}
``````

akhilesh890
New poster
Posts: 1
Joined: Tue Apr 05, 2011 5:43 pm

### FLOYD WARSHALL - GIVING WA

#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
#define INFI 10000000
#define V 200

int main()
{

long long int path[V+1][V+1] , vert , edge, x , y , wt , i , j, k , source , dest , people;

cin >> vert >> edge ;
int c=0;;
while (vert != 0 && edge != 0 )
{
for ( i = 0 ; i <= vert; i++)
for ( j = 0 ; j <= vert ; j++)
{
if ( i != j)
path[j] = -1;
else
path[j] = 0;
}
c++;
while ( edge--)
{
cin >> x >> y >> wt ;
path[x][y] = wt-1;
path[y][x] = wt-1;
}
cin >> source >> dest >> people ;

for ( k = 1 ; k <= vert ; k++ )
{
for ( i = 1 ; i <= vert ; i++ )
{
for ( j = 1 ; j <= vert ; j++ )
{

path[j] = max (path[j] , (min(path[k] , path[k][j])) );
}
}
}
for ( i = 1 ; i <= vert ; i++ )
{ cout << endl;
for ( j = 1 ; j <= vert ; j++ )
{
cout << path[j] << " " ;
}
}

double d = double (double(people) / double (path[source][dest]));
cout <<"Scenario #" <<c<< "\nMinimum Number of Trips = " << ceil (d) << endl;
cin >> vert >> edge ;
}
}

vpanait
New poster
Posts: 17
Joined: Sun Apr 01, 2012 11:01 am

### Re: 10099 - The Tourist Guide

Note: the Guide has also to be on the bus, so do not forget to add him.. i did.. neil_iiita
New poster
Posts: 2
Joined: Thu Nov 29, 2012 12:07 pm

### Re: 10099 - The Tourist Guide

In many problems from this secction, http://uva.onlinejudge.org/index.php?op ... tegory=116, i am getting RE(Runtime Error).
Lets take this problem for example.
Here is my code for problem 10099-The Tourist Guide - http://uva.onlinejudge.org/index.php?op ... oblem=1040.

I am using the concept of Disjoint set to find max-spanning tree. Then i use bfs from start to end node and find the min value of passengers in that path.

Code: Select all

``````#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>
#include <cstring>
#include <string>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <list>

#define fr(a, b, c) for(int a = b; a <= c; a++)
#define mst(a, b) memset(a, b, sizeof(a));

using namespace std;

typedef struct {
int parent;
}nod;
typedef struct {
int from;
int to;
int weight;
}vert;
vert edge;
int parent;
nod node;
int find_parent(int a)
{
if(parent[a] == a)
return a;
else
parent[a] =  find_parent(parent[a]);
}
int is_union(int a, int b)
{
return (find_parent(a) == find_parent(b));
}
void make_union(int c1, int c2)
{
parent[find_parent(c1)] = find_parent(c2);
}
int comp ( const void *a, const void*b)
{
if( ( * ( vert* ) a ).weight < ( *( vert* )b ).weight )
return 1;
return -1;
}

void min_span_tree(int n)
{
fr(i, 1, 1004)
parent[i] = i;
//cout << "going to sort\n";
qsort(edge, n, sizeof(vert), comp);
//cout << "sorted\n\n";
fr (i, 1, n){
if(!is_union(edge[i].from, edge[i].to)) {
make_union(edge[i].from, edge[i].to);
//cout << "\nConnectiong nodes " << edge[i].from << " and " << edge[i].to;
}
}
}
int min_passenger(int a, int b)
{
int min = 10e8;
int temp = node[b].parent;
while(1){
if(temp == a){
break;
}
else{
b = temp;
temp = node[temp].parent;
}
}
return min;
}
int bfs_mod(int a, int b, int n)
{
int visited;
int count = 0, kk = 0;
mst(visited, 0);
queue <int> q;
fr(i, 1, n)
node[i].parent = 0;
list <int> :: iterator it;
fr(i, a, n){
if(visited[i] == 0) {
visited[i] =1;
q.push(i);
}
while(!q.empty()){
kk = q.front();
q.pop();
//cout << "Currently on node " << kk << endl;
//system("pause");
if(!visited[*it]){
visited[*it] = 1;
q.push(*it);
node[*it].parent = kk;
}
}
}
}
return min_passenger(a, b);
}
void clear_all ()
{
//mst(a, 0);
mst(parent, 0);
fr(i, 1, 1002) {
node[i].parent = 0;
}
fr(i, 1, 1003){
edge[i].from = 0;
edge[i].to = 0;
edge[i].weight = 0;
}
}
void print_all(int c, int s)
{
cout << "Printing the edges \n";
fr(i, 1, s){
cout << "\n\nfrom " << edge[i].from ;
cout << "   to " << edge[i].to;
cout << "   weight id " << edge[i].weight;
}
cout << "\n";
cout << "Printing arents of all nodes\n";
fr(i, 1, c)
cout << parent[i] << "   ";
cout << "\n\nPrinting the nodes adjacency list\n";
fr(i, 1, c){
cout << "\nPrinting ajcancy list for node " << i << endl;
list <int> :: iterator it;
cout << *it << "    ";
}
}
int main()
{
int c, s, q, t = 1;
while (1){
int x, y, w;
scanf("%d %d", &c, &s);
if(c == 0 && s == 0)
break;
clear_all();
cout << "Scenario #" << t << endl;;
t++;

//mst(a, 0);
fr(i, 1, s){
scanf("%d %d %d", &x, &y, &w);
edge[i].from = x;
edge[i].to = y;
edge[i].weight = w;
}

min_span_tree(s);
//print_all(c, s);
//fr(i, 1, q){
scanf("%d %d %d", &x, &y, &q);
int mini = ceil(q / (bfs_mod(x, y, c)-1));
cout << "Minimun Number of Trips = " << mini << endl;
cout << "\n";
//break;
}
}
``````

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 10099 - The Tourist Guide

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

neil_iiita
New poster
Posts: 2
Joined: Thu Nov 29, 2012 12:07 pm

### Re: 10099 - The Tourist Guide

What doesn't match? It runs fine on my computer and even on www.ideone.com

achan8501
New poster
Posts: 6
Joined: Mon Nov 05, 2012 9:13 pm

### Re: 10099 - The Tourist Guide

Have you actually check the sample input/output? You code produces

Minimun Number of Trips = 4

when it should be

Minimun Number of Trips = 5

Anyways, your error is in the line with the division and ceiling in the output. 99/24 = 4 since it is an integer division, so ceiling is useless.

thewill
New poster
Posts: 6
Joined: Wed Dec 04, 2013 10:18 am

### WA FOR 10099

HERE IS THE CODE PLZZ LOOK AT IT..
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cctype>
#include <stack>
#include <queue>
#include <vector>
#include <map>
#include <sstream>
#include <set>
#include <math.h>
#define pi acos(-1.0)
#define N 1000000
using namespace std;
int main ()
{
int i,j,k,n,t=0,r;
int wt,a;
int s1,s2,s,d,twt,cnt,temp;
while(scanf("%d%d",&n,&r)==2)
{
if(n==0&&r==0)
{
break;
}
cnt=0;
for(i=0;i<110;i++)
{
for(j=0;j<110;j++)
{
a[j]=-10000;
}
}
for(i=1;i<=n;i++)
{
a=0;
}
for(i=1;i<=r;i++)
{
cin>>s1>>s2>>wt;
a[s1][s2]=wt;
a[s2][s2]=wt;
}
for(k=1;k<=n;k++)
{
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
a[j]=max(a[j],min(a[k],a[k][j]));
}
}
}
cin>>s>>d>>twt;
if(s==d)
{
printf("Scenario #%d\n",++t);
printf("Minimum Number of Trips = 1\n\n");
continue;
}
temp=a[s][d]-1;
cnt=twt/temp;
if(twt%temp!=0)
{
cnt++;
}
printf("Scenario #%d\n",++t);
printf("Minimum Number of Trips = %d\n\n",cnt);
}
return 0;
}

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

### Re: 10099 - The Tourist Guide

here is used bellman ford algorithm wih different relaxation to get the path
but i am getting TLE
here is my code
http://ideone.com/mlyEL1
need help
is it minimax floyd warshal

prashantharshi
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

### Re: 10099 - The Tourist Guide

the question is simply a modification of floyd warshal algo for maximin path
a maximin path =we maximise the path in which edge length is minimum
for(k=0;k<n;k++)
for(i=0;i<n;i++)
for(j=0;j<n;j++)
dist[j]=max(dist[j],min(dist[k],dist[k][j])

http://ideone.com/Gjv9Bo
is my AC code brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: WA FOR 10099

Change line 44 to:
a[s2][s1]=wt;
Check input and AC output for thousands of problems on uDebug!