11635 - Hotel booking

[serur]

I'm getting RE for this...

Code: Select all

/*
 * ``Hotel Booking''
 */
#include <algorithm>
#include <cctype>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
#define N 10001
#define TEN_HOURS (10*60)
#define Q (1UL << 21)
#define MASK(k) ((1UL << (k))-1UL)
#define enc(x,y) ((x)|((y)<<14))
#define xchg(x,y) (((x)==(y))||((x) ^= (y), (y) ^= (x), (x) ^= (y)))
#define bubble {\
		xchg(heap[i],heap[j]);\
		xchg(pos[heap[i]],pos[heap[j]]); }
#define oo 0xfffffffful

int n,h,m,is_hotel[N],yes;
vector<pair<int,int> > adj[N];
unsigned int heap[Q],d[Q];
int cnt,pos[Q];

void heap_push( unsigned int u ) {
	int i,j;

	if ( pos[u] < 0 ) {
		pos[heap[cnt] = u] = cnt;
		++cnt;
	}
	for ( j = pos[u]; j; j = i ) {
		if ( d[heap[i = (j-1)/2]] <= d[heap[j]] )
			break;
		bubble;
	}
}

void heap_pop( unsigned int *u ) {
	int i,j;

	pos[*u = *heap] = -1;
	if ( --cnt )
		pos[heap[0] = heap[cnt]] = 0;
	for ( j = 0;;) {
		i = j, j <<= 1, ++j;
		if ( j > cnt-1 ) break;
		if ( j < cnt-1 && d[heap[j+1]] < d[heap[j]] )
			++j;
		if ( d[heap[i]] <= d[heap[j]] ) break;
		bubble;
	}
}

int main() {
	int i,j,k,t,x,y,dt;
	unsigned int u,v;
#ifndef ONLINE_JUDGE
	freopen("in.txt","r",stdin);
#endif
	while ( 1 == scanf("%d",&n) && n && ++yes ) {
		for ( i = 0; i < n; ++i )
			adj[i].clear();
		for ( scanf("%d",&h), i = 0; i < h; ++i )
			scanf("%d",&j), is_hotel[--j] = yes;
		for ( scanf("%d",&m); m--; ) {
			scanf("%d %d %d",&i,&j,&k);
			--i, --j;
			adj[i].push_back(make_pair(j,k));
			adj[j].push_back(make_pair(i,k));
		}
		memset(d,0xff,sizeof(d));
		d[0] = 0;
		memset(pos,-1,sizeof(pos));
		cnt = 0;
		heap_push(0);

		while ( cnt ) {
			heap_pop(&u), t = d[u];
			x = (u & MASK(14)), k = (u>>14);
			for ( i = 0; i < (int)adj[x].size(); ++i ) {
				pair<int,int> pp = adj[x][i];
				y = pp.first, dt = pp.second;
				if ( t+dt <= TEN_HOURS )
					if ( t+dt < d[v = enc(y,k)] ) {
						d[v] = t+dt;
						heap_push(v);	
					}
				if ( is_hotel[x] == yes ) {
					//assert( dt <= TEN_HOURS );
					if ( dt <= TEN_HOURS )
					if ( dt < d[v = enc(y,k+1)] ) {
						d[v] = dt;
						heap_push(v);
					}
				}
			}
		}
		for ( k = 0, j = -1; k <= h; ++k )
			if ( d[enc(n-1,k)] < +oo ) {
				j = k;
				break;
			}
		printf("%d\n",j);
	}
	return 0;
}

[Jehad Uddin]

Getting WA in this prob,pls help getting frustrated

Code: Select all

#include<iostream>
#include<string>
#include<map>
#include<queue>
#include<algorithm>
#include<vector>
#include<math.h>
#include<stdlib.h>
#define INF 900000000

using namespace std;

struct ss
{
    int tim,ht,pos;
};
int dis[10005][1005];

class comp{
    public : bool operator()(const ss &a,const ss &b)
    {
        return a.tim>b.tim;
    }
};
priority_queue<ss,vector<ss>,comp>Q;
vector<ss>edge[10005];
int n,m;
int h[10005];
int hh;
void ini()
{
    int i,j,k;
    for(i=0;i<=n;i++)
    {

        edge[i].clear();
        h[i]=0;
        for(j=0;j<=hh;j++) dis[i][j]=INF;

    }
    while(!Q.empty()) Q.pop();
}

void dijk()
{
    int i,j,k,l,u,v,t;
    ss s1,s2,s3,s4;
    s1.ht=0,s1.tim=0,s1.pos=1;
    dis[1][0]=0;
    Q.push(s1);
    while(!Q.empty())
    {
        s1=Q.top();
        Q.pop();
        u=s1.pos;
        //cout<<u<<" "<<s1.ht<<" "<<s1.tim<<endl;
        for(i=0;i<edge[u].size();i++)
        {
            s2=edge[u][i];
            v=s2.pos;
            if(s2.tim+s1.tim<dis[v][s1.ht]&&s2.tim+s1.tim<=(s1.ht+1)*600)
            {
                dis[v][s1.ht]=s2.tim+s1.tim;
                s3.ht=s1.ht,s3.pos=v,s3.tim=s2.tim+s1.tim;
                Q.push(s3);
            }
        }

        if(s1.tim%600!=0)
        {
            k=s1.tim/600;
            k=k+1;
            if(h[u]==1)
            {
                s3.ht=k,s3.tim=k*600,s3.pos=u;
                Q.push(s3);
            }
        }
    }
    k=INF;
    for(i=0;i<=hh;i++) if(dis[n][i]<k) k=dis[n][i],j=i;
    if(k!=INF) printf("%d\n",j);
    else
    printf("-1\n");
}

int main()
{
    int i,j,k,u,v,t;
    ss s1,s2;
    while(scanf("%d",&n)==1&&n)
    {

        scanf("%d",&hh);
        ini();
        for(i=0;i<hh;i++)
        {
            scanf("%d",&j);
            h[j]=1;
        }
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            scanf("%d%d%d",&u,&v,&t);
            s1.pos=v,s1.ht=0,s1.tim=t,s2.pos=u,s2.ht=0,s2.tim=t;
            edge[u].push_back(s1),edge[v].push_back(s2);
        }
        dijk();

    }
    return 0;
}

[LifeMaker]

i'm really interested in knowing the correct approach to this problem, so can anyone please reply to this thread

i tried different approaches, but they all failed. now i got AC but in 2.7 seconds (so clearly my algo. isn't good and there are much better ones)

the idea of my soln is that i apply dijkstra k times with each hotel as a source (i regard nodes 1 and n hotels as well), so now i have a smaller graph: g[k+2][k+2], which represents the all pair all dest. shortest paths between hotels (including node #1, #n).
then i apply bfs on this new graph from node #1 to get the shortest path to the destination. (in the graph g[][], 2 nodes i,j share an edge if g[j]<=600).

so, what is the best approach to this problem??

thanks in advance

[zobayer]

I have also got WA. Here is my approach, tell me what is wrong here...

Lets say, weight here is a pair, first element, number of days (i.e. number of hotels) and second one is total minute continuing on that day.

Now, I run a dijkstra from 1 and try to reach N maintaining this:
if the current city is reachable (i.e. doesn't need more than 600 minutes from previous continuation) then
----> if it is a hotel then
--------> he may stay here, so day + 1 and continuation minutes becomes 0, push this state if possible
----> else he may not stay here, and continue his travel, so, days stay same, and minutes = minutes + current edge cost
else he just tries to continue, i.e. days stay same, and minutes = minutes + current edge cost.

finally the optimal days in N is my answer, here, I considered that, 1 and N don't have any hotel (as they will be useless and I removed if given any)

So, here is my code, if anyone wants to have a look

Code: Select all

#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <string>
#include <vector>
#include <list>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <algorithm>
#include <iterator>
#include <utility>
using namespace std;

template< class T > T _abs(T n) { return (n < 0 ? -n : n); }
template< class T > T _max(T a, T b) { return (!(a < b) ? a : b); }
template< class T > T _min(T a, T b) { return (a < b ? a : b); }
template< class T > T sq(T x) { return x * x; }
template< class T > T gcd(T a, T b) { return (b != 0 ? gcd<T>(b, a%b) : a); }
template< class T > T lcm(T a, T b) { return (a / gcd<T>(a, b) * b); }
template< class T > bool inside(T a, T b, T c) { return a<=b && b<=c; }
template< class T > void setmax(T &a, T b) { if(a < b) a = b; }
template< class T > void setmin(T &a, T b) { if(b < a) a = b; }

#define MP(x, y) make_pair(x, y)
#define REV(s, e) reverse(s, e)
#define SET(p) memset(p, -1, sizeof(p))
#define CLR(p) memset(p, 0, sizeof(p))
#define MEM(p, v) memset(p, v, sizeof(p))
#define CPY(d, s) memcpy(d, s, sizeof(s))
#define READ(f) freopen(f, "r", stdin)
#define WRITE(f) freopen(f, "w", stdout)
#define ALL(c) c.begin(), c.end()
#define SIZE(c) (int)c.size()
#define PB(x) push_back(x)
#define ff first
#define ss second
#define i64 long long
#define ld long double
#define pii pair< int, int >
#define psi pair< string, int >

const double EPS = 1e-9;
const double BIG = 1e19;
const int INF = 0x3f3f3f3f;
const int MAX = 10001;
const int LMT = 600;

typedef pair< pii, pii > edge;

vector< pii > G[MAX];
pii d[MAX][2];
bool flag[MAX][2], hotel[MAX];

int dijkstra(int s, int n) {
	int u, v, w, h;
	priority_queue< edge, vector< edge >, greater< edge > > Q;
	d[s][0] = pii(0, 0);
	hotel[s] = hotel[n] = 0;
	Q.push(edge(d[s][0], pii(s, 0)));
	while(!Q.empty()) {
		edge e = Q.top(); Q.pop();
		u = e.ss.ff, h = e.ss.ss;
		if(u == n) return e.ff.ff;
		if(flag[u][h]) continue;
		if(d[u][h] < e.ff) continue;
		for(int i = 0; i < SIZE(G[u]); i++) {
			v = G[u][i].ss;
			w = G[u][i].ff;
			if(hotel[v]) {
				if(!flag[v][0]) {
					if(d[u][h].ss + w <= LMT && d[v][0] > pii(d[u][h].ff, d[u][h].ss + w)) {
						d[v][0] = pii(d[u][h].ff, d[u][h].ss + w);
						Q.push(edge(d[v][0], pii(v, 0)));
					}
				}
				if(!flag[v][1]) {
					if(d[u][h].ss + w <= LMT && d[v][1] > pii(d[u][h].ff + 1, 0)) {
						d[v][1] = pii(d[u][h].ff + 1, 0);
						Q.push(edge(d[v][1], pii(v, 1)));
					}
				}
			}
			else {
				if(!flag[v][0]) {
					if(d[u][h].ss + w <= LMT && d[v][0] > pii(d[u][h].ff, d[u][h].ss + w)) {
						d[v][0] = pii(d[u][h].ff, d[u][h].ss + w);
						Q.push(edge(d[v][0], pii(v, 0)));
					}
				}
			}
		}
		flag[u][h] = 1;
	}
	return -1;
}

int main() {
	//READ("in.txt");
	//WRITE("out.txt");
	int n, e, k, i, u, v, w, ret;
	while(scanf("%d", &n)==1 && n) {
		for(i = 1; i <= n; i++) {
			G[i].clear();
			hotel[i] = flag[i][0] = flag[i][1] = 0;
			d[i][0] = d[i][1] = pii(INF, INF);
		}
		scanf("%d", &k);
		for(i = 0; i < k; i++) {
			scanf("%d", &e);
			hotel[e] = 1;
		}
		scanf("%d", &e);
		for(i = 0; i < e; i++) {
			scanf("%d%d%d", &u, &v, &w);
			G[u].PB(pii(w, v));
			G[v].PB(pii(w, u));
		}
		ret = dijkstra(1, n);
		printf("%d\n", ret);
	}
	return 0;
}

Thanks in advance.

[smilitude]

Your use of

Code: Select all

if(flag[u][h]) continue;

looks suspicious to me. You can enter a node with different minutes in hand - but i think your program will not consider all of them.

[zobayer]

Your use of

Code: Select all

if(flag[u][h]) continue;

looks suspicious to me. You can enter a node with different minutes in hand - but i think your program will not consider all of them.

You are right.. indeed it was the bug.

[chengouxuan]

i'm really interested in knowing the correct approach to this problem, so can anyone please reply to this thread

i tried different approaches, but they all failed. now i got AC but in 2.7 seconds (so clearly my algo. isn't good and there are much better ones)

the idea of my soln is that i apply dijkstra k times with each hotel as a source (i regard nodes 1 and n hotels as well), so now i have a smaller graph: g[k+2][k+2], which represents the all pair all dest. shortest paths between hotels (including node #1, #n).
then i apply bfs on this new graph from node #1 to get the shortest path to the destination. (in the graph g[][], 2 nodes i,j share an edge if g[j]<=600).

so, what is the best approach to this problem??

thanks in advance

consider d[] to be the distance from the source vertex to any vertex in Dijkstra algorithm, v is the vertex with minimal d[] and is poped from the heap. d[v] never decrease. and we just need the vertexs which d[] <= 600. so quit Dijkstra as soon as you have popped a vertexs v and d[v] > 600. using this method, i have optimized my solution from 2.2 seconds to 0.9 seconds.

[annedoxia122]

Code: Select all

#include "stdafx.h"
002
#include "roomType.h"
003
#include "hotelClient.h"
004
#include "HotelReservation.h"
005
#include <iostream>
006
#include <typeinfo>
007
#include <ctime>
008
#include <vector>
009
#include <fstream>
010
#include <string>
011
#include <exception>
012
 
013
using namespace std;
014
 
015
void loadFiles();
016
void displayMain();
017
void addRoomMenu();
018
void addClientMenu();
019
void requestReservation();
020
void displayRooms();
021
void displayClients();
022
void displayReservations();
023
void quit();
024
bool checkNumerical();
025
void getString(string message, string &s);
026
bool answerBoolConv(string answer);
027
bool getDate(int room, int &posDay1, int &posMonth1, int &posYear1, int &posDay2, int &posMonth2, int &posYear2);
028
 
029
template <class Type>
030
void getInput(string message, Type &x);
031
 
032
vector<roomType> rooms;
033
vector<hotelClient> clients;
034
vector<HotelReservation> reservations;
035
const string reservationMonth = "January";
036
const int maxReserved = 10;
037
 
038
int main()
039
{
040
    loadFiles();
041
    displayMain();
042
    return 0;
043
}
044
 
045
void loadFiles()
046
{
047
    ifstream file;
048
    file.exceptions ( ifstream::eofbit | ifstream::failbit | ifstream::badbit );
049
     
050
    roomType tempRoom;
051
         
052
    try
053
    {
054
        int count = 0;
055
        file.open("c:\\clientFile.txt");
056
 
057
        if (!file.eof())
058
            file >> count;
059
         
060
        for (int i = 0; i < count; i++)
061
        {
062
            int tempID;
063
            string tempFirst;
064
            string tempLast;
065
            char temp[250];
066
            string mailing;
067
            long long phone;
068
            string CCNum;
069
            double tempBalanceDue;
070
            string CCType;
071
 
072
            file >> tempID;
073
            file >> tempFirst;
074
            file >> tempLast;
075
            file.ignore();
076
            file.getline(temp, 250);
077
            mailing = static_cast<string>(temp);
078
            file >> phone;
079
            file >> CCNum;
080
            file >> CCType;
081
            file >> tempBalanceDue;
082
             
083
            hotelClient tempClient;
084
            tempClient.setClient(tempFirst, tempLast, mailing, phone, CCNum, CCType, tempID, tempBalanceDue);
085
            clients.push_back(tempClient);
086
        }
087
        file.close();
088
    }
089
    catch(exception &e)
090
    {
091
        cout << e.what() << " +Error trying to open clientFile.txt" << endl;
092
        file.clear();
093
        system("pause");
094
    }
095
         
096
    try
097
    {
098
        int count = 0;
099
        file.open("c:\\roomFile.txt");
100
 
101
        if (!file.eof())
102
            file >> count;
103
         
104
        for (int i = 0; i < count; i++)
105
        {
106
            int roomNo;
107
            double cost;
108
            bool smoking, twobeds, suite;
109
 
110
            file >> roomNo;
111
            file >> cost;
112
            file >> smoking;
113
            file >> twobeds;
114
            file >> suite;
115
             
116
            roomType temp(roomNo, cost, twobeds, smoking, suite);
117
            rooms.push_back(temp);
118
             
119
        }
120
        file.close();
121
    }
122
    catch(exception &e)
123
    {
124
        cout << e.what() << " +Error trying to open roomFile.txt" << endl;
125
        file.clear();
126
        system("pause");
127
    }
128
 
129
    try
130
    {
131
        int count = 0;
132
        file.open("c:\\reservationFile.txt");
133
 
134
        if (!file.eof())
135
            file >> count;
136
         
137
        for (int i = 0; i < count; i++)
138
        {
139
            int clientID;
140
            int reservNo;
141
            int roomNo;
142
            double cost;
143
            int day1, month1, year1, day2, month2, year2;
144
 
145
            file >> clientID;
146
            file >> reservNo;
147
            file >> roomNo;
148
            file >> cost;
149
            file >> day1 >> month1 >> year1;
150
            file >> day2 >> month2 >> year2;
151
 
152
            HotelReservation temp(clientID, roomNo, reservNo, cost, day1, month1, year1, day2, month2, year2);
153
            reservations.push_back(temp);
154
             
155
        }
156
        file.close();
157
    }
158
    catch(exception &e)
159
    {
160
        cout << e.what() << " +Error trying to open reservationFile.txt" << endl;
161
        file.clear();
162
        system("pause");
163
    }
164
}
165
 
166
void displayMain()
167
{
168
    system("cls");
169
 
170
     
171
     
172
 
173
    int selection;
174
 
175
    do
176
    {
177
        cout << "***********MAIN************" << endl;
178
        cout << "1.) add client" << endl;
179
        cout << "2.) display rooms" << endl;
180
        cout << "3.) display clients" << endl;
181
        cout << "4.) request reservation" << endl;
182
        cout << "5.) display reservations" << endl;
183
        cout << "6.) exit" << endl << endl;
184
        cout << "Selection: ";
185
        cin >> selection;
186
    }
187
    while (selection <= 0 && selection >= 8);
188
 
189
    switch (selection)
190
    {
191
    case 1:
192
        addClientMenu();
193
        break;
194
    case 2:
195
        displayRooms();
196
        break;
197
    case 3:
198
        displayClients();
199
        break;
200
    case 4:
201
        requestReservation();
202
        break;
203
    case 5:
204
        displayReservations();
205
        break;
206
    case 6: //leave blank
207
    default:
208
        quit();
209
    }
210
}
211
 
212
void addRoomMenu()
213
{
214
    int newRoomNumber = 1;
215
    bool smoking;
216
    bool suite;
217
    bool twoBeds;
218
    double costPerDay;
219
    string tempChar;
220
     
221
    if (rooms.size() != 0)
222
        newRoomNumber = rooms[rooms.size() - 1].getRoomNumber() + 1;
223
 
224
    system("cls");
225
 
226
     
227
    getInput("What is the cost per day? ", costPerDay);
228
    getString("Is this room smoking? (Y/N): ", tempChar);
229
    smoking = answerBoolConv(tempChar);
230
    getString("Is this new room a suite? (Y/N): ", tempChar);
231
    suite = answerBoolConv(tempChar);
232
    getString("Does this new room have two beds? (Y/N): ", tempChar);
233
    twoBeds = answerBoolConv(tempChar);
234
 
235
    roomType tempRoom(newRoomNumber, costPerDay, twoBeds, smoking, suite);
236
    rooms.push_back(tempRoom);
237
    cout << "The room has been created!" << endl;
238
    system("pause");
239
 
240
    displayMain();
241
}
242
 
243
void addClientMenu()
244
{
245
    int tempID;
246
    string tempFirst;
247
    string tempLast;
248
    string mailing;
249
    long long phoneNo;
250
    string creditNum;
251
    string CCType;
252
    double tempBalanceDue;
253
 
254
    system("cls");
255
 
256
    if(clients.size() == 0)
257
        tempID = 1111;
258
    else
259
        tempID = clients[clients.size() - 1].getCustomerID() + 1;
260
 
261
    cin.clear();
262
    cin.ignore(250, '\n');
263
 
264
    getString("What is the first name? ", tempFirst);
265
    getString("What is the last name? ", tempLast);
266
    getString("What is the mailing address? ", mailing);
267
    getInput("What is the phone number? (no dashes or spaces) ", phoneNo);
268
    getString("What is the credit card number? (no dashes or spaces) ", creditNum);
269
    getString("What is the credit card type? ", CCType);
270
    tempBalanceDue = 0;
271
 
272
    hotelClient tempClient(tempFirst, tempLast, mailing, phoneNo, creditNum, CCType, tempID, tempBalanceDue);
273
 
274
    clients.push_back(tempClient);
275
    cout << endl;
276
    cout << "A new client has been added!" << endl;
277
    system("pause");
278
    displayMain();
279
}
280
 
281
 
282
void requestReservation()
283
{
284
    system("cls");
285
     
286
    int clientID;
287
    int clientVecNum;
288
    getInput("Enter the client Identification number: ", clientID);
289
    bool exists = false;
290
    for (unsigned int i = 0; i < clients.size(); i++)
291
    {
292
        if (clientID == clients[i].getCustomerID())
293
        {
294
            exists = true;
295
            clientVecNum = i;
296
        }
297
 
298
    }
299
    if (exists)
300
    {
301
        bool available = false;
302
         
303
        do
304
        {
305
            bool roomNoRequested = false;
306
            string answer;
307
            cout << "Would you like to request a room by number? (Y/N): ";
308
            cin >> answer;
309
            cout << endl;
310
            roomNoRequested = answerBoolConv(answer);
311
            if (roomNoRequested)
312
            {
313
                int roomNumber;
314
                getInput("What room number would you like to request? : ", roomNumber);
315
                 
316
                bool reserved = false;
317
                int day, month, year, toDay, toMonth, toYear;
318
                reserved = getDate(roomNumber, day, month, year, toDay, toMonth, toYear);
319
 
320
                if(reserved == true)
321
                {
322
                    cout << "Room is unavailable for renting at that time or doesn't exist" << endl;
323
                    system("pause");
324
                    available = false;
325
                    break;
326
                }
327
                else
328
                {
329
                    bool roomReady = false;
330
                    int vecNum;
331
                    int reservationNumber = 11111111;
332
                    if (reservations.size() != 0)
333
                        reservationNumber = reservations[reservations.size() - 1].getReservationNum() + 1;
334
 
335
                    for (unsigned int i = 0; i < rooms.size(); i++)
336
                    {
337
                        if (roomNumber == rooms[i].getRoomNumber())
338
                        {
339
                            vecNum = i;
340
                        }
341
                    }
342
                     
343
                    HotelReservation temp(clientID, rooms[vecNum].getRoomNumber(), reservationNumber, day, month, year, toDay, toMonth, toYear);
344
                    temp.setCost(rooms[vecNum].getCost() * temp.getReservationLength());
345
                    clients[clientVecNum].SetBalanceDue(clients[clientVecNum].getBalanceDue() + temp.getCost());
346
                    reservations.push_back(temp);
347
                    cout << "The room is available and is now reserved for clientID " << clientID << "." << endl << endl;
348
                    system("pause");
349
                    available = true;
350
                    break;
351
                }
352
            }
353
             
354
            else
355
            {
356
                bool suite;
357
                bool smoking;
358
                bool twoBeds;
359
                string answer;
360
                cin.get();
361
                getString("Would you like a suite? (Y/N) : ", answer);
362
                suite = answerBoolConv(answer);
363
                cout << endl;
364
                getString("Would you like a smoking room? (Y/N) : ", answer);
365
                smoking = answerBoolConv(answer);
366
                cout << endl;
367
                getString("Would you like two beds? (Y/N) : ", answer);
368
                twoBeds = answerBoolConv(answer);
369
                cout << endl;
370
                vector<roomType> possibleRoomMatch;
371
                vector<bool> roomAvail;
372
 
373
                for (unsigned int i = 0; i < rooms.size(); i++)
374
                {
375
                    roomAvail.push_back(true);
376
                    if(rooms[i].getSuite() == suite)
377
                        possibleRoomMatch.push_back(rooms[i]);
378
                    else
379
                        roomAvail[i] = false;
380
                }
381
                for (unsigned int i = 0; i < rooms.size(); i++)
382
                {
383
                    if(rooms[i].getSmoking() == smoking)
384
                    {
385
                        bool alreadyThere = false;
386
                        for (unsigned int z = 0; i < possibleRoomMatch.size(); i++)
387
                        {
388
                            if(possibleRoomMatch[z].getRoomNumber() == rooms[i].getRoomNumber())
389
                                alreadyThere = true;
390
                        }
391
                        if(alreadyThere == false)
392
                        {
393
                            if(roomAvail[i])
394
                                possibleRoomMatch.push_back(rooms[i]);
395
                        }
396
                    }
397
                    else
398
                        roomAvail[i] = false;
399
                }
400
                for (unsigned int i = 0; i < rooms.size(); i++)
401
                {
402
                    if(rooms[i].getTwoBeds() == twoBeds)
403
                    {
404
                        bool alreadyThere = false;
405
                        for (unsigned int z = 0; i < possibleRoomMatch.size(); i++)
406
                        {
407
                            if(possibleRoomMatch[z].getRoomNumber() == rooms[i].getRoomNumber())
408
                                alreadyThere = true;
409
                        }
410
                        if(alreadyThere == false)
411
                        {
412
                            if(roomAvail[i])
413
                                possibleRoomMatch.push_back(rooms[i]);
414
                        }
415
                    }
416
                    else
417
                        roomAvail[i] = false;
418
                }
419
                bool matchFound = false;
420
                int d1, d2, m1, m2, y1, y2, room, roomVec;
421
                for (unsigned int i = 0; i < possibleRoomMatch.size(); i++)
422
                {
423
                    if(roomAvail[i])
424
                    {
425
                        if(!getDate(possibleRoomMatch[i].getRoomNumber(), d1, m1, y1, d2, m2, y2))
426
                        {
427
                            room = possibleRoomMatch[i].getRoomNumber();
428
                            roomVec = i;
429
                            matchFound = true;
430
                            break;
431
                        }
432
                    }
433
                }
434
                if(matchFound == true)
435
                {
436
                    int reservationNumber = 11111111;
437
                    if (reservations.size() != 0)
438
                        reservationNumber = reservations[reservations.size() - 1].getReservationNum() + 1;
439
                    HotelReservation temp(clientID, room, reservationNumber, d1, m1, y1, d2, m2, y2);
440
                    temp.setCost(temp.getReservationLength() * rooms[roomVec].getCost());
441
                    clients[clientVecNum].SetBalanceDue(clients[clientVecNum].getBalanceDue() + temp.getCost());
442
                    reservations.push_back(temp);
443
                    cout << "The room is available and is now reserved for clientID " << clientID << "." << endl << endl;
444
                    system("pause");
445
                    available = true;
446
                }
447
                else
448
                {
449
                    cout << "Sorry, there is no match available at this time" << endl << endl;
450
                    system("pause");
451
                    available = false;
452
                }
453
            }
454
        }
455
        while (available = false);
456
         
457
    }
458
    else
459
    {
460
        cout << "Client does not exist!!" << endl << endl;
461
        system("pause");
462
    }
463
    displayMain();
464
}
465
bool answerBoolConv(string answer)
466
{
467
    if (answer == "Y" || answer == "y")
468
        return true;
469
    else
470
        return false;
471
}
472
 
473
void displayRooms()
474
{
475
    system("cls");
476
    for (unsigned int i = 0; i < rooms.size(); i++)
477
        cout << rooms[i] << endl;
478
 
479
    cout << endl;
480
    system("pause");
481
    displayMain();
482
}
483
 
484
void displayClients()
485
{
486
    system("cls");
487
    for (unsigned int i = 0; i < clients.size(); i++)
488
        cout << clients[i] << endl << endl;
489
 
490
    system("pause");
491
    displayMain();
492
}
493
 
494
void displayReservations()
495
{
496
    system("cls");
497
    for (unsigned int i = 0; i < reservations.size(); i++)
498
        cout << reservations[i] << endl;
499
 
500
    system("pause");
501
    displayMain();
502
}
503
void quit()
504
{
505
    ofstream clientFile("c:\\clientFile.txt", ios::out);
506
 
507
    clientFile << clients.size() << endl;
508
    for(unsigned int i = 0; i < clients.size(); i++)
509
    {
510
        clientFile << clients[i].getCustomerID() << " ";
511
        clientFile << clients[i].getFirstName() << " ";
512
        clientFile << clients[i].getLastName() << endl;
513
        clientFile << clients[i].getMailingAddress() << endl;
514
        clientFile << clients[i].getPhoneNumber() << " ";
515
        clientFile << clients[i].getCreditCard() << " ";
516
        clientFile << clients[i].getCreditCardType() << " ";
517
        clientFile << clients[i].getBalanceDue() << " ";
518
        clientFile << endl;
519
    }
520
 
521
    ofstream reservationFile("c:\\reservationFile.txt", ios::out);
522
 
523
    reservationFile << reservations.size() << endl;
524
    for(unsigned int i = 0; i < reservations.size(); i++)
525
    {
526
        reservationFile << reservations[i].getClientId() << " ";
527
        reservationFile << reservations[i].getReservationNum() << " ";
528
        reservationFile << reservations[i].getRoomNumber() << " ";
529
        reservationFile << reservations[i].getCost() << " ";
530
        reservationFile << reservations[i];
531
        reservationFile << endl;
532
    }
533
}
534
 
535
template <class Type>
536
void getInput(string message, Type &x)
537
{
538
    do
539
    {  
540
        Type temp = 0;
541
        cout << message;
542
        cin >> temp;
543
        cout << endl;
544
        x = temp;
545
        cin.ignore();
546
    }
547
    while(!checkNumerical());
548
}
549
 
550
bool checkNumerical()
551
{
552
    if (!cin)
553
    {
554
        cout << "You entered an incorrect value, try again" << endl;
555
        cin.clear();
556
        cin.ignore(1000, '\n');
557
        return false;
558
    }
559
    else
560
        return true;
561
}
562
 
563
void getString(string message, string &s)
564
{
565
    cin.clear();
566
    char temp[250];
567
    cout << message;
568
    cin.getline(temp, 250);
569
    s = static_cast<string>(temp);
570
}
571
bool getDate(int room, int &posDay1, int &posMonth1, int &posYear1, int &posDay2, int &posMonth2, int &posYear2)
572
{
573
    system("cls");
574
    // Check to see if the room even exists first
575
    int roomVecNum = -1;
576
    int test = rooms.size();
577
    for (unsigned int i = 0; i < rooms.size(); i++)
578
    {
579
        if(rooms[i].getRoomNumber() == room)
580
        {
581
            roomVecNum = i;
582
            break;
583
        }
584
    }
585
    if(roomVecNum == -1)
586
        return true;
587
 
588
    cout << "You will now enter the starting date for the reservation..." << endl;
589
 
590
    int selection;
591
    do
592
    {
593
        cout << "Select a month" << endl;
594
        cout << "1.) Jan" << endl;
595
        cout << "2.) Feb" << endl;
596
        cout << "3.) Mar" << endl;
597
        cout << "4.) Apr" << endl;
598
        cout << "5.) May" << endl;
599
        cout << "6.) Jun" << endl;
600
        cout << "7.) Jul" << endl;
601
        cout << "8.) Aug" << endl;
602
        cout << "9.) Sep" << endl;
603
        cout << "10.) Oct" << endl;
604
        cout << "11.) Nov" << endl;
605
        cout << "12.) Dec" << endl;
606
        getInput("Selection: ", selection);
607
    }
608
    while (selection < 1 || selection > 12);
609
    posMonth1 = selection;
610
     
611
    do
612
    {
613
        getInput("Select a day (1-28) :", selection);
614
    }
615
    while (selection < 1 || selection > 28);
616
 
617
    posDay1 = selection;
618
     
619
    do
620
    {
621
        getInput("Select a year (2008 to 2011) :", selection);
622
    }
623
    while (selection < 2008 || selection > 2011);
624
 
625
    posYear1 = selection;
626
 
627
    system("cls");
628
    cout << "You will now enter an ending date for the reservation" << endl;
629
     
630
    do
631
    {
632
        cout << "Select a month" << endl;
633
        cout << "1.) Jan" << endl;
634
        cout << "2.) Feb" << endl;
635
        cout << "3.) Mar" << endl;
636
        cout << "4.) Apr" << endl;
637
        cout << "5.) May" << endl;
638
        cout << "6.) Jun" << endl;
639
        cout << "7.) Jul" << endl;
640
        cout << "8.) Aug" << endl;
641
        cout << "9.) Sep" << endl;
642
        cout << "10.) Oct" << endl;
643
        cout << "11.) Nov" << endl;
644
        cout << "12.) Dec" << endl;
645
        getInput("Selection: ", selection);
646
    }
647
    while (selection < 1 || selection > 12);
648
    posMonth2 = selection;
649
     
650
    do
651
    {
652
        getInput("Select a day (1-28) :", selection);
653
    }
654
    while (selection < 1 || selection > 28);
655
 
656
    posDay2 = selection;
657
     
658
    do
659
    {
660
        getInput("Select a year (2008 to 2011) :", selection);
661
    }
662
    while (selection < 2008 || selection > 2011);
663
 
664
    posYear2 = selection;
665
 
666
    time_t todayDate;
667
    time_t date2;
668
    time_t date3;
669
 
670
    time(&todayDate);
671
    struct tm date2str = {0,0,0,posDay1,posMonth1 - 1,posYear1 - 1900};
672
    struct tm date3str = {0,0,0,posDay2,posMonth2 - 1,posYear2 - 1900};
673
    //start = mktime(&today);
674
    date2 = mktime(&date2str);
675
    date3 = mktime(&date2str);
676
         
677
    double difference = difftime(date2, todayDate) / (60 * 60 * 24);
678
    if (difference < 0)
679
    {
680
        cout << "You entered a date from the past" << endl;
681
        system("pause");
682
        return true;
683
    }
684
     
685
    difference = -1;
686
 
687
    difference = difftime(date3, date2) / (60 * 60 * 24);
688
    if (difference < 0)
689
    {
690
        cout << "Your start date was after your end date!" << endl;
691
        system("pause");
692
        return true;
693
    }
694
 
695
    int days = static_cast<int>(difference);
696
 
697
    //Check if the room is not already reserved.
698
 
699
    time_t testDate;
700
    for(unsigned int x = 0; x < reservations.size(); x++)
701
    {
702
        testDate = reservations[x].getReservationstart();
703
        for(int y = 0; y <= days; y++)
704
        {
705
            for(int z = 0; z <= reservations[x].getReservationLength(); z++)
706
            {
707
                if(date2 == testDate)
708
                {
709
                    return true;
710
                }
711
                testDate = testDate + (60 * 60 * 24);
712
            }
713
            date2 = date2 + (60 * 60 * 24);
714
        }
715
    }
716
    return false;
717
     
718
}

This reference code might help you.

[mahade hasan]

edited but still RE.....
getting RE ..........Why plz help me..........

Code: Select all

#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
const int infinity = 1000000000;

struct data {
    long city,H, dist;
    bool operator < ( const data& p ) const {
        return dist > p.dist;
    }
};



int main()
{
   long I,K,L,M,N,NoCity,NoHtl,NoRut;
   
   while(scanf("%ld",&NoCity)&&NoCity>0)
   {
      scanf("%ld",&NoHtl);
      bool Hotel[110]={0};
      while(NoHtl--)
      {
         scanf("%ld",&K);
         Hotel[K]=1;
      }
      
      vector<long> Edge[10009],Cost[10009];
      scanf("%ld",&NoRut);
      while(NoRut--)
      {
         scanf("%d %d %d",&I,&K,&L);
         Edge[I].push_back(K);
         Edge[K].push_back(I);
         Cost[I].push_back(L);
         Cost[K].push_back(L);
      }
      
      bool Status[10009]={0};
      N=infinity;
      priority_queue<data>Q;
      data u,v;
      
      u.city=1;
      u.dist=0;
      u.H=0;
      
      Q.push(u);
      while(!Q.empty())
      {
         u=Q.top();
         Q.pop();
         if(u.city==NoCity&&N>u.H) {N=u.H;continue;}
         for(I=0;I<Edge[u.city].size();I++)
         {
            v.city=Edge[u.city][I];
            v.dist=u.dist+Cost[u.city][I];
            v.H=u.H;
            if(v.dist>600)
            {
               if(Status[v.city]==0&&Hotel[u.city]==1)
               {
                  ++v.H;
                  Q.push(v);
                  Status[v.city]=1;
               }
            }
            else if(Status[v.city]==0)
            Status[v.city]=1,Q.push(v);
            
         }
      }
      if(N==infinity) printf("-1\n");
      else printf("%d\n",N);
   }
   
   return 0;
}

[/color]

[brianfry713]

There could be a hotel in city 9999.

[mahade hasan]

There could be a hotel in city 9999.

edited but still RE......

Code: Select all

#include<iostream>
#include<stdio.h>
#include<queue>
#include<vector>
using namespace std;
const int infinity = 1000000000;

struct data {
    long city,H, dist;
    bool operator < ( const data& p ) const {
        return dist > p.dist;
    }
};



int main()
{
   long I,K,L,M,N,NoCity,NoHtl,NoRut;
   
   while(scanf("%ld",&NoCity)&&NoCity>0)
   {
      scanf("%ld",&NoHtl);
      bool Hotel[110]={0};
      while(NoHtl--)
      {
         scanf("%ld",&K);
         Hotel[K]=1;
      }
      
      vector<long> Edge[10009],Cost[10009];
      scanf("%ld",&NoRut);
      while(NoRut--)
      {
         scanf("%d %d %d",&I,&K,&L);
         Edge[I].push_back(K);
         Edge[K].push_back(I);
         Cost[I].push_back(L);
         Cost[K].push_back(L);
      }
      
      bool Status[10009]={0};
      N=infinity;
      priority_queue<data>Q;
      data u,v;
      
      u.city=1;
      u.dist=0;
      u.H=0;
      
      Q.push(u);
      while(!Q.empty())
      {
         u=Q.top();
         Q.pop();
         if(u.city==NoCity&&N>u.H) {N=u.H;continue;}
         for(I=0;I<Edge[u.city].size();I++)
         {
            v.city=Edge[u.city][I];
            v.dist=u.dist+Cost[u.city][I];
            v.H=u.H;
            if(v.dist>600)
            {
               if(Status[v.city]==0&&Hotel[u.city]==1)
               {
                  ++v.H;
                  Q.push(v);
                  Status[v.city]=1;
               }
            }
            else if(Status[v.city]==0)
            Status[v.city]=1,Q.push(v);
            
         }
      }
      if(N==infinity) printf("-1\n");
      else printf("%d\n",N);
   }
   
   return 0;
}

[/color]

[brianfry713]

Try input:

Code: Select all

10000
1 9999
2
1 9999 600
9999 10000 600
0

Output should be 1.

[mahade hasan]

plz give some critical input for this problem ..........

[brianfry713]

Try input:

Code: Select all

10000
1 9999
2
1 9999 600
9999 10000 600
0

Output should be 1.

Your code produces an RE because your Hotel array is only size 110 and there could be a hotel in city 9999.

[mahade hasan]

plz give some critical input for this problem ..........

because after correction it gives WA.............