11635 - Hotel booking

[brianfry713]

Post your updated code.

[mahade hasan]

Post your updated code.

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]

[brianfry713]

Input:

Code: Select all

4
1 2
3
1 2 300
2 3 300
3 4 300
0

AC output: 1

[zxjcarrot]

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){
			addEdge(sG,index,i,1);
		}
	}
}


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);
			addEdge(g,u,v,w);
			addEdge(g,v,u,w);
		}
		for (i=0;i<hotNum.size();++i)
		{
			spfa(hotNum[i],i);
		}
		cout<<bfs(0,1)<<endl;
	}
	return 0;
}

[lbv]

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]

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]

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

[brianfry713]

info on SE at: http://uva.onlinejudge.org/index.php?op ... 1&Itemid=1

[jakecho1]

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;
   vector<pair<int,int> > adj;
   Town() {
      hotel=false;
	  min=0x3f3f3f3f;
	  day=0x3f3f3f3f;
	  adj.clear();
   }
};
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 num_of_road;
	 cin >> num_of_road;
	 for(int i=0;i<num_of_road;i++) {
	    int t1, t2, length;
		cin >> t1 >> t2 >> length;
		map[t1].adj.push_back(make_pair<int,int>(t2,length));
		map[t2].adj.push_back(make_pair<int,int>(t1,length));
		if(map[t1].hotel) {
			map[t2].adj.push_back(make_pair<int,int>(t1+10000,length));
			map[t1+10000].adj.push_back(make_pair<int,int>(t2,length));
		}
		if(map[t2].hotel) {
			map[t1].adj.push_back(make_pair<int,int>(t2+10000,length));
			map[t2+10000].adj.push_back(make_pair<int,int>(t1,length));			 
		}
	 }
	 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> >&a=tptr->adj;
	   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]

Input:

Code: Select all

2
1 2
1
1 2 1
0

AC output:

Code: Select all

0

[catweazle352]

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

[lbv]

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]

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

[Target979]

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;
     vector<edge> links;
     node(): hotel(false), hv(false),t(1000),v(0){links.clear();}
};

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;
	  }
	  for (edge link : city.links){
	       int next = link.d;
	       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;
	       towns[a].links.push_back(edge(b,t));
	       towns[b].links.push_back(edge(a,t));
	  }
	  int hn = solve(n);     
	  hn >= 0 ? cout << hn : cout << -1;
	  cout << endl;
	  turn = 0;
     }
     return 0;
}

[catweazle352]

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