10099 - The Tourist Guide

[data_br]

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

[sajnt]

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

[rein08]

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

[valkov]

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]

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[101];
};

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


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

int main(void) 
{
    Node nodes[101]; //the array of nodes of our adjacency list 
    int bandwidthTable[101][101]; //the table of bandwidths for our algorithm
    Edge edges[101]; //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][0]--; 
        //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[][101])
{
    for(int i = 0; i < 101; i++)
        for(int j = 0; j < 101; j++)
            bandwidthTable[i][j] = LONG_MAX; 
}

[akhilesh890]

Can anyone please help me out here - I am using floyd warshall algorithm using optimal routing yet giving wrong answer.


#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]

Note: the Guide has also to be on the bus, so do not forget to add him.. i did..

[neil_iiita]

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.
Please help me out. The solution is giving right answer for many test cases, but ultimately REfrom the judge.

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;
    list <int> adj;
}nod;
typedef struct {
    int from;
    int to;
    int weight;
}vert;
vert edge[1008];
int parent[1002];
nod node[1005];
int adj[1003][1003];
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);
            node[edge[i].from].adj.push_back(edge[i].to);
            node[edge[i].to].adj.push_back(edge[i].from);
            //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){
            if(adj[b][temp] < min)
                min = adj[b][temp];
            break;
        }
        else{
            if(adj[temp][b] < min)
                min = adj[temp][b];
            b = temp;
            temp = node[temp].parent;
        }
    }
    return min;
}
int bfs_mod(int a, int b, int n)
{
    int visited[1003];
    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");
            for(it = node[kk].adj.begin(); it != node[kk].adj.end(); it++){
                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);
    mst(adj, 0);
    fr(i, 1, 1002) {
        node[i].parent = 0;
        node[i].adj.clear();
    }
    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;
        for(it = node[i].adj.begin(); it != node[i].adj.end(); 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;
            adj[y][x] = w;
            adj[x][y] = 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]

Doesn't match the sample I/O.

[neil_iiita]

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

[achan8501]

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]

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[110][110];
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]

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]

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]

Change line 44 to:
a[s2][s1]=wt;