## 11635 - Hotel booking

Moderator: Board moderators

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

### Re: 11635--Hotel Booking

Check input and AC output for thousands of problems on uDebug!

Learning poster
Posts: 87
Joined: Thu Dec 15, 2011 3:08 pm

### Re: 11635--Hotel Booking

geting WA,,,,,,,,,,

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[100003]={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]
we r surrounded by happiness
need eyes to feel it!

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

### Re: 11635--Hotel Booking

Input:

Code: Select all

``````4
1 2
3
1 2 300
2 3 300
3 4 300
0``````
AC output: 1
Check input and AC output for thousands of problems on uDebug!

zxjcarrot
New poster
Posts: 2
Joined: Mon Jan 14, 2013 4:14 am

### Re: 11635--Hotel Booking

what's the bottleneck of my prog? I'm geting TLE.

Code: Select all

``````#include <iostream>
#include <map>
#include <vector>
#include <cstdio>
#include <queue>
#include <memory.h>
using namespace std;

#define MAX 10001
typedef struct Edge
{
int i,v;
Edge *next;
Edge(int ii=0,int vv=0,Edge * nnext=NULL):i(ii),v(vv),next(nnext){}
};

vector<int> hotNum;
Edge g[MAX];
Edge sG[105];
int dis[MAX];
bool vis[MAX];
bool svis[105];
int sdis[105];
int n,m,q;

int bfs(int start,int end){
memset(sdis,0,sizeof(sdis));
memset(svis,0,sizeof(svis));
queue<int> q;
q.push(start);
vis[start]=1;
while (q.size())
{
int t=q.front();
q.pop();
if(t==end)return sdis[t]-1;
Edge * n=sG[t].next;
for (;n;n=n->next)
{
if(!vis[n->i]){
sdis[n->i]=sdis[t]+1;
vis[n->i]=1;
q.push(n->i);
}
}
}
return -1;
}
void addEdge(Edge g[MAX],int u,int v,int w){
Edge *n=&g[u];
while (n->next)
{
n=n->next;
}
n->next=new Edge(v,w);
n->next->next=NULL;
}
void spfa(int start,int index){
memset(dis,0X7F,sizeof(int)*(n+1));
memset(vis,0,sizeof(bool)*(n+1));
dis[start]=0;
queue<int>q;
q.push(start);
vis[start]=1;
while (q.size())
{
int t=q.front();
q.pop();
vis[t]=0;
Edge *n=g[t].next;
for (;n;n=n->next)
{
if(dis[n->i]>dis[t]+n->v){
dis[n->i]=dis[t]+n->v;
if(!vis[n->i]){
vis[n->i]=1;
q.push(n->i);
}
}
}
}
for (int i=0;i<hotNum.size();++i)
{
if(i==index)continue;
if(dis[hotNum[i]]<=600){
}
}
}

int main(){
while (cin>>n,n)
{
int i;
cin>>q;
hotNum.clear();
memset(g,0,sizeof(g[0])*(n+1));
memset(sG,0,sizeof(sG));
hotNum.push_back(1);
hotNum.push_back(n);
for (i=0;i<q;++i)
{
int t;
scanf("%d",&t);
if(t!=1&&t!=n)
hotNum.push_back(t);
}
cin>>m;
for (i=0;i<m;++i)
{
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
}
for (i=0;i<hotNum.size();++i)
{
spfa(hotNum[i],i);
}
cout<<bfs(0,1)<<endl;
}
return 0;
}
``````

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

### Re: 11635--Hotel Booking

zxjcarrot wrote:what's the bottleneck of my prog? I'm geting TLE.
Doing a quick profile of your code, it seems that most of the time is spent inside the spfa function (about 86% of the total runtime), but I wouldn't call it a bottleneck, it's more of a problem with the complexity of your algorithm.

If I understand correctly, you run a BFS from every hotel, and in the BFS, every node and edge that is reachable from each hotel is visited at least once. Think about the time complexity of that approach. Consider other classic algorithms like Dijkstra's SSSP to build your solution.

zxjcarrot
New poster
Posts: 2
Joined: Mon Jan 14, 2013 4:14 am

### Re: 11635--Hotel Booking

lbv wrote:
zxjcarrot wrote:what's the bottleneck of my prog? I'm geting TLE.
Doing a quick profile of your code, it seems that most of the time is spent inside the spfa function (about 86% of the total runtime), but I wouldn't call it a bottleneck, it's more of a problem with the complexity of your algorithm.

If I understand correctly, you run a BFS from every hotel, and in the BFS, every node and edge that is reachable from each hotel is visited at least once. Think about the time complexity of that approach. Consider other classic algorithms like Dijkstra's SSSP to build your solution.
thanks,I'll try.

ruippeixotog
New poster
Posts: 1
Joined: Wed Sep 25, 2013 12:29 am

### Re: 11635--Hotel Booking

All submissions for this problem since 19 May 2013 were given a Submission Error. Is there any problem with the grader?

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

### Re: 11635--Hotel Booking

Check input and AC output for thousands of problems on uDebug!

jakecho1
New poster
Posts: 2
Joined: Mon Feb 10, 2014 4:18 am

### Re: 11635--Hotel Booking

WA plz help.
I splitted towns if the town has a hotel for the driver. Use a prioirty_queue to implement the heap. Otherwise is pretty simple straight dijkstra.

Code: Select all

``````#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <vector>
#include <queue>
#include <utility>
using namespace std;
class Town {
public:
bool hotel;
int min;
int day;
Town() {
hotel=false;
min=0x3f3f3f3f;
day=0x3f3f3f3f;
}
};
class Comp {
public:
bool operator () (Town* ptr1, Town* ptr2) {
if(ptr1->day!=ptr2->day) return (ptr1->day > ptr2->day);
if(ptr1->min!=ptr2->min) return (ptr1->min > ptr2->min);
return false;
}
};
Town map[20001];
const int debug =0;
int main() {
int num_of_town;
while(cin >> num_of_town && num_of_town!=0){
for(int i=1;i<=num_of_town;i++)map[i]=Town();
for(int i=1;i<=num_of_town;i++)map[i+10000]=Town();
int num_of_hotel;
cin >> num_of_hotel;
for(int i=0;i<num_of_hotel;i++){
int t;
cin >>t;
map[t].hotel=true;
}
int t1, t2, length;
cin >> t1 >> t2 >> length;
if(map[t1].hotel) {
}
if(map[t2].hotel) {
}
}
priority_queue<Town*,vector<Town*>,Comp> qu;
qu=priority_queue<Town*,vector<Town*>,Comp>();
map[1].day=map[1].min=0;
qu.push(&map[1]);
while(!qu.empty() && qu.top()!=&map[num_of_town] ) {
Town* tptr=qu.top();

vector<pair<int,int> >::iterator it = a.begin();
for(;it!=a.end();it++) {
int dst=it->first;
int time=it->second;
if((tptr->min+time)<=600 ){
if(map[dst].hotel && (tptr->day < map[dst].day-1)){
map[dst].day=tptr->day+1;
map[dst].min=0;
qu.push(&map[dst]);
} else if (!map[dst].hotel &&  (tptr->day!=map[dst].day || (tptr->day==map[dst].day &&
tptr->min+time < map[dst].min) )) {
map[dst].day=tptr->day;
map[dst].min=tptr->min + time;
qu.push(&map[dst]);
}
}
}
qu.pop();
}
if(!qu.empty()) {
cout << map[num_of_town].day << endl;
} else {
cout << -1 <<endl;
}
}
return 0;
}
``````

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

### Re: 11635--Hotel Booking

Input:

Code: Select all

``````2
1 2
1
1 2 1
0
``````
AC output:

Code: Select all

``0``
Check input and AC output for thousands of problems on uDebug!

catweazle352
New poster
Posts: 10
Joined: Wed Aug 14, 2013 7:53 pm

### Re: 11635--Hotel Booking

My code passes all test cases of this thread, but I still get WA. My approach is a modified dijkstra where my distance is a pair of count of hotels slept and drive distance since the last hotel I slept in.

During dijkstra I get the next node from my priority queue (using stl multimap), check the distance. If the distance is too large, I look for the last hotel visited on my way so far and update the priority queue by first deleting and then re-inserting that node in order to reflect distance changes.

Any critical testcases greatly appreciated.

My code:

Code: Select all

``````#include <iostream>
#include <map>
#include <vector>
#include <limits.h>
#include <stdio.h>

using namespace std;

struct _NODE;

typedef struct
{
int driveDistance;              // distance I am driving since last slept
int distLastHotel;              // distance to last passed hotel, where I did not sleep
int cHotelsSlept;               // number of hotels I slept in
} DIST, *PDIST;

typedef pair<_NODE *, int> EDGE, *PEDGE;

typedef struct _NODE
{
int predecessor;            // the node before
bool visited;               // visited during dijkstra algorithm
int id;                     // the id of the node
bool isHotel;               // is it a hotel?
DIST distance;              // distance to source node
vector<EDGE> edges;         // my edges
} NODE, *PNODE;

typedef bool (*PFNCOMP)(const DIST&, const DIST&);
typedef multimap<DIST, PNODE, PFNCOMP> NODEMAP, *PNODEMAP;

int g_MAXDISTANCE = 600;
int g_BIGHOTELDISTANCE = 1000;

bool distLess( const DIST &distLeft, const DIST &distRight)
{
int diff = distLeft.cHotelsSlept - distRight.cHotelsSlept;
bool less = (diff < 0 ? true :
( diff > 0 ? false :
( distLeft.driveDistance < distRight.driveDistance)));
return less;
}

void calcDist( NODE &nodeSrc, EDGE &edge, PDIST pDist )
{
PNODE pNodeDest = edge.first;

// check if I can reach the destination
int oldDistance = nodeSrc.distance.driveDistance;
int driveDistance = (oldDistance == INT_MAX) ? INT_MAX : oldDistance + edge.second;

// distance too large?
if( driveDistance > ::g_MAXDISTANCE ) {
// try to sleep in formely visited hotel
if( (nodeSrc.distance.distLastHotel != INT_MAX) && (nodeSrc.distance.distLastHotel + edge.second <= ::g_MAXDISTANCE) ) {
pDist->cHotelsSlept = nodeSrc.distance.cHotelsSlept + 1;
pDist->driveDistance = nodeSrc.distance.distLastHotel + edge.second;
pDist->distLastHotel = pNodeDest->isHotel ? 0 : INT_MAX;
}
// cannot sleep => node not reachable
else {
pDist->cHotelsSlept = g_BIGHOTELDISTANCE;
pDist->driveDistance = INT_MAX;
pDist->distLastHotel = INT_MAX;
}
}
// distance ok, and dest node is a hotel.
else if( pNodeDest->isHotel) {
pDist->cHotelsSlept = nodeSrc.distance.cHotelsSlept;
pDist->distLastHotel = 0;
pDist->driveDistance = nodeSrc.distance.driveDistance+edge.second;
}
// distance ok and no hotel
else {
pDist->cHotelsSlept = nodeSrc.distance.cHotelsSlept;
pDist->distLastHotel = (nodeSrc.distance.distLastHotel == INT_MAX) ? INT_MAX : nodeSrc.distance.distLastHotel + edge.second;
pDist->driveDistance = (nodeSrc.distance.driveDistance == INT_MAX) ? INT_MAX : nodeSrc.distance.driveDistance + edge.second;
}
}

void updateMap( NODEMAP &nodesNotVisited, PNODE pNode, DIST &distNew, bool fInsert )
{
NODEMAP::iterator it = nodesNotVisited.find( pNode->distance);
while( (it->second != pNode) &&   (it != nodesNotVisited.end()) )
it++;
if( it != nodesNotVisited.end() )
{
nodesNotVisited.erase( it );
if( fInsert )
{
pNode->distance.cHotelsSlept = distNew.cHotelsSlept;
pNode->distance.driveDistance = distNew.driveDistance;
pNode->distance.distLastHotel= distNew.distLastHotel;
nodesNotVisited.insert( pair<DIST, PNODE>(pNode->distance, pNode) );
}
}
}

int solve( NODEMAP &nodesNotVisited, int idSrc, int idDest )
{
int maxDistance = -1;
bool fLoop = (nodesNotVisited.size() > 0);
while( fLoop )
{
// get node with shortest distance
PNODE pNodeMin = nodesNotVisited.begin()->second;

// if its the destination node, are we finished
if( pNodeMin->id == idDest )
{
maxDistance = pNodeMin->distance.cHotelsSlept;
if( maxDistance >= g_BIGHOTELDISTANCE)
maxDistance = -1;
fLoop = false;
}
// if this node already has too big a hotel distance, then there is no solution at all
else if( pNodeMin->distance.cHotelsSlept < g_BIGHOTELDISTANCE )
{
int cEdges = pNodeMin->edges.size();

// check all edges of this node in order to get shorter paths
for( int idxEdge = 0; idxEdge < cEdges; ++idxEdge )
{
PEDGE pEdge = &(pNodeMin->edges[idxEdge]);
PNODE pNodeDest = pEdge->first;
DIST newDist; calcDist( *pNodeMin, *pEdge, &newDist);
if( distLess( newDist, pNodeDest->distance))
{
updateMap( nodesNotVisited, pNodeDest, newDist, true);
pNodeDest->predecessor = pNodeMin->id;
}
}

// remove node with the shortest distance from the multimap
pNodeMin->visited = true;
updateMap( nodesNotVisited, pNodeMin, pNodeMin->distance, false);

// check if loop is finished
if( nodesNotVisited.size() == 0 )
fLoop = false;
else if( pNodeMin->id == idDest ) {
fLoop = false; maxDistance = pNodeMin->distance.cHotelsSlept;
}
}
else {
fLoop = false;
}
}

return maxDistance;
}

int main()
{
vector<int> solutions;

while( true )
{
// get number of cities
int cCities = 0; scanf( "%d", &cCities ); if( cCities == 0 ) break;

// allocate an array and fill it with the nodes
PNODE aNodes = new NODE[cCities];
for( int idx = 0; idx < cCities; ++idx )
{
aNodes[idx].distance.cHotelsSlept = aNodes[idx].distance.driveDistance =
( idx == 0 ? 0 : INT_MAX);
aNodes[idx].distance.distLastHotel = INT_MAX;
aNodes[idx].id = idx+1;
aNodes[idx].predecessor = 0;
aNodes[idx].isHotel = false;
aNodes[idx].visited = false;
}

// get hotels
int cHotels = 0; scanf( "%d", &cHotels);
for( int idxH = 0; idxH < cHotels; ++idxH)
{
int h = 0;
if( idxH+1 < cHotels )
scanf( "%d", &h);
else
scanf( "%d", &h);
aNodes[h-1].isHotel = true;
}

// get edges
int cEdges = 0; scanf( "%d", &cEdges);
for( int idxE = 0; idxE < cEdges; ++idxE)
{
int nodeSrc = -1, nodeDest = -1, dist = -1;
scanf("%d %d %d", &nodeSrc, &nodeDest, &dist);
PNODE pNodeSrc = &(aNodes[nodeSrc-1]), pNodeDest = &(aNodes[nodeDest-1]);
pNodeSrc->edges.push_back(EDGE( pNodeDest, dist ));
pNodeDest->edges.push_back(EDGE( pNodeSrc, dist ));
}

// construct the nodemap
NODEMAP nodesNotVisited( distLess );
for( int idx = 0; idx < cCities; ++idx)
{
PNODE pNode = &(aNodes[idx]);
nodesNotVisited.insert( pair<DIST, PNODE>(pNode->distance,pNode));
}

// solve the test case
int solution = solve( nodesNotVisited, 1, cCities);
solutions.push_back( solution );
}

int cSolutions = solutions.size();
for(int idx = 0; idx < cSolutions; idx++)
{
printf( "%d\n", solutions[idx] );
}
}
``````
It's easy to beef about something - but it's much harder to make it better

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

### Re: 11635--Hotel Booking

catweazle352 wrote:My code passes all test cases of this thread, but I still get WA. (..)
Any critical testcases greatly appreciated.
You may try:

Input

Code: Select all

``````9
6 4 8 2 3 6 5
8
1 6 476
7 5 49
2 9 488
5 4 151
5 8 537
2 7 367
1 6 509
6 7 430

6
4 2 4 1 6
11
5 2 328
6 3 249
3 5 150
5 4 501
5 1 220
3 5 520
4 1 378
3 2 116
4 1 476
1 3 418
4 2 562

9
4 5 2 6 7
16
3 5 280
7 5 419
2 8 226
7 1 135
3 9 413
8 3 293
4 1 76
5 3 490
7 5 16
1 7 271
3 8 148
1 5 438
6 4 237
8 1 129
5 3 217
3 2 165

0
``````
Output

Code: Select all

``````3
1
1
``````

catweazle352
New poster
Posts: 10
Joined: Wed Aug 14, 2013 7:53 pm

### Re: 11635--Hotel Booking

Hi lbv,

thank you for your test cases. Using those I found my mistake, because they revealed a case I did not take into concern.

Christof
It's easy to beef about something - but it's much harder to make it better

Target979
New poster
Posts: 5
Joined: Wed Oct 08, 2014 10:52 am

### Re: 11635 - Hotel booking

I'm getting wrong answer, but can't seem to find the problem. Does anyone have a hint or suggestion what to take a closer look at?

Code: Select all

``````#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct edge
{
int d,t;
edge(int din,int tin): d(din), t(tin){};
};

struct node
{
bool hotel,hv;
int t,v;
};

node towns[10001];
queue<int> hoteltv;
int turn=0;

bool bfs(int start, int goal)
{
queue<int> visit;
visit.push(start);
towns[start].v = turn;
towns[start].t = 0;
while(!visit.empty()){
int current = visit.front();
visit.pop();
if (current == goal){
return true;
}
node& city = towns[current];
if (!city.hv && city.hotel){;
hoteltv.push(current);
city.hv=1;
}
int tv = link.t + city.t;
if (tv <= 600 && (towns[next].v != turn || tv < towns[next].t))
{
towns[next].v = turn;
towns[next].t = tv;
visit.push(next);
}
}
}
return false;
}

int solve(int goal)
{
if(bfs(1,goal))
return turn;
while(!hoteltv.empty()){
turn++;
int n = hoteltv.size();
for (int i = 0; i < n; i++){
int start = hoteltv.front();
hoteltv.pop();
if(bfs(start,goal))
return turn;
}
}
return -1;
}

int main()
{
int n, h, a, b,t, m;
while(cin>>n && n!=0){
cin >> h;
for (int i = 0; i <= n; i++){
towns[i] = node();
}
for (int i = 0; i <h; i++){
cin >> a;
towns[a].hotel = true;
}
cin >> m;
for (int i = 0; i < m; i++){
cin >> a >> b >> t;
}
int hn = solve(n);
hn >= 0 ? cout << hn : cout << -1;
cout << endl;
turn = 0;
}
return 0;
}
``````

catweazle352
New poster
Posts: 10
Joined: Wed Aug 14, 2013 7:53 pm

### Re: 11635 - Hotel booking

Hi,

did you take into account that there are cases in which you have to visit an edge more than once? See the test cases above.

Kind Regards

Christof
It's easy to beef about something - but it's much harder to make it better