UVa 11374 - Airport Express

Accepted date: 2016-06-14
Run Time: 0.000
Ranking (as of 2016-06-14): 42 out of 412
Language: C++

/*
  UVa 11374 - Airport Express

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

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

const int N_max = 500;

struct edge {
  int v_;
  int w_;
  int commercial_; // 1 for Commercial-Xpress, 0 for Economy-Xpress
  edge(int v, int w, int commercial) : v_(v), w_(w), commercial_(commercial) {}
};

vector<edge> edges[N_max + 1];
bool dvisited[N_max + 1][2];
int distances[N_max + 1][2];
  // distances[i][0/1] is the min. time to vertex i using Commercial-Xpress (1) or not (0)

struct path {
  int u_, commercial_;
} paths[N_max + 1][2];

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

void print_path(int u, int c, int& cu)
{
  if (paths[u][c].u_ == -1)
    printf("%d", u);
  else {
    if (c && !paths[u][c].commercial_)
      cu = paths[u][c].u_;
    print_path(paths[u][c].u_, paths[u][c].commercial_, cu);
    printf(" %d", u);
  }
}

int main()
{
  int N, S, E;
  bool printed = false;
  while (scanf("%d %d %d", &N, &S, &E) != EOF) {
    if (printed)
      putchar('\n');
    else
      printed = true;
    for (int i = 1; i <= N; i++) {
      edges[i].clear();
      dvisited[i][0] = dvisited[i][1] = false;
      distances[i][0] = distances[i][1] = numeric_limits<int>::max();
    }
    int M;
    scanf("%d", &M);
    while (M--) {
      int X, Y, Z;
      scanf("%d %d %d", &X, &Y, &Z);
      edges[X].push_back(edge(Y, Z, 0));
      edges[Y].push_back(edge(X, Z, 0));
    }
    int K;
    scanf("%d", &K);
    while (K--) {
      int X, Y, Z;
      scanf("%d %d %d", &X, &Y, &Z);
      edges[X].push_back(edge(Y, Z, 1));
      edges[Y].push_back(edge(X, Z, 1));
    }
    // apply the Dijkstra's shortest path algorithm
    set<pair<int, int>, distance_comparator> pq; // priority queue
    distances[S][0] = 0;
    paths[S][0].u_ = -1;
    pq.insert(make_pair(S, 0));
    int min_t, min_c;
    while(!pq.empty()) {
      pair<int, int> p = *pq.begin();
      pq.erase(pq.begin());
      int u = p.first, cc = p.second, t = distances[u][cc];
      dvisited[u][cc] = true;
#ifdef DEBUG
      printf("[%d][%d]: %d\n", u, cc, t);
#endif
      if (u == E) {
        min_t = t, min_c = cc;
        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_, c = es[i].commercial_;
        if (c) {
          if (!cc && !dvisited[v][1] && t + w < distances[v][1]) {
            pair<int, int> q = make_pair(v, 1);
            pq.erase(q);
            distances[v][1] = t + w, paths[v][1].u_ = u, paths[v][1].commercial_ = cc;
#ifdef DEBUG
            printf("  [%d][1]: %d\n", v, distances[v][1]);
#endif
            pq.insert(q);
          }
        }
        else {
          if (!dvisited[v][cc] && t + w < distances[v][cc]) {
            pair<int, int> q = make_pair(v, cc);
            pq.erase(q);
            distances[v][cc] = t + w, paths[v][cc].u_ = u, paths[v][cc].commercial_ = cc;
#ifdef DEBUG
            printf("  [%d][%d]: %d\n", v, cc, distances[v][cc]);
#endif
            pq.insert(q);
          }
        }
      }
    }
    int cu = -1;
    print_path(E, min_c, cu);
    if (cu != -1)
      printf("\n%d\n", cu);
    else
      printf("\nTicket Not Used\n");
    printf("%d\n", min_t);
  }
  return 0;
}