11635 - Hotel booking
Moderator: Board moderators
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11635--Hotel Booking
Post your updated code.
Check input and AC output for thousands of problems on uDebug!
- mahade hasan
- Learning poster
- Posts: 87
- Joined: Thu Dec 15, 2011 3:08 pm
- Location: University of Rajshahi,Bangladesh
Re: 11635--Hotel Booking
geting WA,,,,,,,,,,brianfry713 wrote:Post your updated code.
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;
}
we r surrounded by happiness
need eyes to feel it!
need eyes to feel it!
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11635--Hotel Booking
Input:AC output: 1
Code: Select all
4
1 2
3
1 2 300
2 3 300
3 4 300
0
Check input and AC output for thousands of problems on uDebug!
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){
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;
}
Re: 11635--Hotel Booking
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.zxjcarrot wrote:what's the bottleneck of my prog? I'm geting TLE.
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.
Re: 11635--Hotel Booking
thanks,I'll try.lbv wrote: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.zxjcarrot wrote:what's the bottleneck of my prog? I'm geting TLE.
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.
-
- 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?
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11635--Hotel Booking
info on SE at: http://uva.onlinejudge.org/index.php?op ... 1&Itemid=1
Check input and AC output for thousands of problems on uDebug!
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.
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;
}
-
- Guru
- Posts: 5947
- Joined: Thu Sep 01, 2011 9:09 am
- Location: San Jose, CA, USA
Re: 11635--Hotel Booking
Input:AC output:
Code: Select all
2
1 2
1
1 2 1
0
Code: Select all
0
Check input and AC output for thousands of problems on uDebug!
-
- 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:
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
Re: 11635--Hotel Booking
You may try:catweazle352 wrote:My code passes all test cases of this thread, but I still get WA. (..)
Any critical testcases greatly appreciated.
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
Code: Select all
3
1
1
-
- 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
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
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;
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;
}
-
- 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
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