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

Grazyna
New poster
Posts: 16
Joined: Wed Apr 20, 2005 2:44 pm
Location: Thessaloniki,Greece

Post by Grazyna » Fri Jul 14, 2006 6:32 pm

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.
I had mistake in reading the data 
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

Post by rhsumon » Wed Jun 27, 2007 7:43 pm

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:

Post by 898989 » Wed Jun 27, 2007 8:14 pm

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.
Mostafa Saad

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

Post by rhsumon » Wed Jun 27, 2007 9:15 pm

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:

Post by 898989 » Wed Jun 27, 2007 10:51 pm

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.
Mostafa Saad

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Jun 27, 2007 11:11 pm

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

Post by rhsumon » Thu Jun 28, 2007 2:07 pm

Thank u jaan .......... it's a silly mistake
Now i got AC
thnx again

Thnks also to 898989 vai
for ur help about 24/25

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Thu Jun 28, 2007 2:18 pm

Remove your code, please.
Ami ekhono shopno dekhi...
HomePage

User avatar
N@$!M
New poster
Posts: 10
Joined: Wed Jan 10, 2007 7:26 pm

Post by N@$!M » Tue Sep 18, 2007 12:07 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.
Bangladesh.

e-Mail Address:
tariqmnasim@gmail.com

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

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

Post by willima » Wed Oct 03, 2007 3:55 pm

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

Post by yjwoo14 » Wed Jan 09, 2008 6:06 am

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

Post by slxst » Sat Jan 12, 2008 8:03 pm

yjwoo14 wrote:I don`t know.. what`s wrong? Plz Help me :cry:
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

Post by yjwoo14 » Mon Jan 14, 2008 12:39 pm

.. 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
Location: (CSE,DU) Dhaka,Bangladesh

Post by turcse143 » Fri Mar 14, 2008 5:24 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

Post by x140l31 » Fri Sep 12, 2008 3:21 am

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);
            minRoads[x][y] = t;
        }

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

        int start, end, pass, trips = 0;
        scanf("%d %d %d", &start, &end, &pass);
        if (start > end) swap(start, end);
        if (start != end) trips = ceil(double(pass)/(minRoads[start][end] - 1));
        printf("Scenario #%d\n", sce++);
        printf("Minimum Number of Trips = %d\n\n", trips);
    }
}
I always get WA :(

Post Reply

Return to “Volume 100 (10000-10099)”