10099 - The Tourist Guide

[Grazyna]

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]

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]

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)

[rhsumon]

Thnx for help but yet i got WA plz check my code here.......

Code: Select all

Removed			

Plz help;;;;;;;;;;;;;;;;;;

[898989]

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

[Jan]

Use

Code: Select all

printf("Scenario #%d\n",c);

Hope it helps.

[rhsumon]

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]

Remove your code, please.

[N@$!M]

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;
}

[willima]

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.

[yjwoo14]

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

[slxst]

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:

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]

.. Because of Initialize..

That is 2-th Array;;;;;

Couldn`t Initialize memset

[turcse143]

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.

[x140l31]

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