10099 - The Tourist Guide

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

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

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

Post by data_br » Sat Aug 08, 2009 4:25 pm

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

Post by sajnt » Sun Jun 20, 2010 4:05 pm

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

Post by rein08 » Thu Jul 22, 2010 1:55 pm

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

Post by valkov » Sun Aug 15, 2010 2:20 pm

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 :P

jenovano2sko
New poster
Posts: 5
Joined: Tue Oct 19, 2010 8:07 am

Re: 10099 - The Tourist Guide

Post by jenovano2sko » Tue Oct 19, 2010 8:12 am

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
New poster
Posts: 1
Joined: Tue Apr 05, 2011 5:43 pm

FLOYD WARSHALL - GIVING WA

Post by akhilesh890 » Thu Apr 07, 2011 4:27 pm

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
New poster
Posts: 17
Joined: Sun Apr 01, 2012 11:01 am

Re: 10099 - The Tourist Guide

Post by vpanait » Wed Jun 06, 2012 11:25 pm

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

Post by neil_iiita » Thu Nov 29, 2012 12:19 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10099 - The Tourist Guide

Post by brianfry713 » Fri Nov 30, 2012 6:45 am

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

Post by neil_iiita » Sun Dec 02, 2012 2:29 pm

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

Post by achan8501 » Wed Dec 05, 2012 12:59 pm

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

Post by thewill » Sat May 24, 2014 8:00 pm

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
New poster
Posts: 22
Joined: Wed May 21, 2014 10:16 am

Re: 10099 - The Tourist Guide

Post by prashantharshi » Sat Jun 07, 2014 8:39 am

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

Post by prashantharshi » Sat Jun 07, 2014 12:38 pm

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 :roll:

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

Re: WA FOR 10099

Post by brianfry713 » Wed Jun 11, 2014 11:03 pm

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

Post Reply

Return to “Volume 100 (10000-10099)”