UVa 11635 - Hotel booking

Accepted date: 2016-04-23
Run Time: 0.430
Ranking (as of 2016-04-23): 23 out of 464
Language: C++

/*
  UVa 11635 - Hotel booking

  To build using Visual Studio 2012:
    cl -EHsc -O2 UVa_11635_Hotel_booking.cpp
*/

#include <vector>
#include <set>
#include <limits>
#include <cstdio>
using namespace std;

const int n_max = 10000, h_max = 100, minutes_max = 10 * 60;

struct edge {
  int v_;
  int w_;
  edge(int v, int w) : v_(v), w_(w) {}
};

bool hotels[n_max + 1], visited[n_max + 1][h_max + 1];
vector<edge> edges[n_max + 1];

struct distance_comparator {
  vector< vector<int> >& distances_;

  distance_comparator(vector< vector<int> >& distances) : distances_(distances) {}
  bool operator() (const pair<int, int>& i, const pair<int, int>& j) const
  {
    if (i.second != j.second)
      return i.second < j.second;
    int di = distances_[i.first][i.second], dj = distances_[j.first][j.second];
    return (di != dj) ? di < dj : i.first < j.first;
  }
};

int main()
{
  while (true) {
    int n;
    scanf("%d", &n);
    if (!n)
      break;
    int h;
    scanf("%d", &h);
    for (int i = 1; i <= n; i++) {
      hotels[i] = false;
      edges[i].clear();
      for (int j = 0; j <= h; j++)
        visited[i][j] = false;
    }
    for (int i = 0; i < h; i++) {
      int c;
      scanf("%d", &c);
      hotels[c] = true;
    }
    int m;
    scanf("%d", &m);
    while (m--) {
      int a, b, t;
      scanf("%d %d %d", &a, &b, &t);
      edges[a].push_back(edge(b, t));
      edges[b].push_back(edge(a, t));
    }
    // apply the Dijkstra's shortest path algorithm
    vector< vector<int> > distances(n + 1, vector<int>(h + 1, numeric_limits<int>::max()));
    set<pair<int, int>, distance_comparator> pq(distances); // priority queue
    distances[1][0] = 0;
    pq.insert(make_pair(1, 0));
    int min_d = -1;
    while(!pq.empty()) {
      pair<int, int> p = *pq.begin();
      pq.erase(pq.begin());
      int u = p.first, d = p.second, t = distances[u][d];
      visited[u][d] = true;
#ifdef DEBUG
      printf("%d %d %d\n", u, d, t);
#endif
      if (u == n) {
        min_d = d;
        break;
      }
      const vector<edge>& es = edges[u];
      for (size_t i = 0, j = es.size(); i < j; i++) {
        int v = es[i].v_, w = es[i].w_;
        if (t + w <= minutes_max &&
          !visited[v][d] && t + w < distances[v][d]) {
          pair<int, int> q = make_pair(v, d);
          pq.erase(q);
          distances[v][d] = t + w;
#ifdef DEBUG
          printf("  %d %d %d\n", v, d, distances[v][d]);
#endif
          pq.insert(q);
        }
        if (hotels[u] && d < h && w <= minutes_max &&
          !visited[v][d + 1] && w < distances[v][d + 1]) {
          pair<int, int> q = make_pair(v, d + 1);
          pq.erase(q);
          distances[v][d + 1] = w;
#ifdef DEBUG
          printf("  %d %d %d\n", v, d + 1, distances[v][d + 1]);
#endif
          pq.insert(q);
        }
      }
    }
    printf("%d\n", min_d);
  }
  return 0;
}