UVa 157 - Route Finding

Accepted date: 2016-07-28
Run Time: 0.000
Ranking (as of 2016-07-28): 145 out of 492
Language: C++

/*
  UVa 157 - Route Finding

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

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <limits>
#include <cstdio>
using namespace std;

const int infinite = numeric_limits<int>::max();
const int nr_letters = 'z' - 'a' + 1, n_max = nr_letters * nr_letters;

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

vector<edge> edges[n_max];
bool visited[n_max];
int distances[n_max], parents[n_max];

struct distance_comparator {
  bool operator() (int i, int j) const
  {
    return (distances[i] != distances[j]) ? distances[i] < distances[j] : i < j;
  }
};

int dijkstra_shortest_path(int n, int start, int end)
{
  for (int i = 0; i < n; i++)
    visited[i] = false, distances[i] = infinite;
  set<int, distance_comparator> pq; // priority queue
  distances[start] = 0, parents[start] = -1;
  pq.insert(start);
  while(!pq.empty()) {
    int u = *pq.begin();
    pq.erase(pq.begin());
    visited[u] = true;
    if (u == end)
      break;
    int d = distances[u], pw = (u != start) ? d - distances[parents[u]] : -1;
    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 (w == 3 && (pw == 3 || pw == 0)) // pass through several connections
        w = 0;
      if (!visited[v] && distances[v] > d + w) {
        pq.erase(v); // remove v if it has already been in the queue
        distances[v] = d + w, parents[v] = u;
        pq.insert(v);
      }
    }
  }
  return distances[end];
}

map<pair<char, char>, int> vertices;
map< int, pair<char, char> > stations;

int get_vertex(char cr, char cs)
{
  pair<map<pair<char, char>, int>::iterator, bool> result =
    vertices.insert(make_pair(make_pair(cr, cs), static_cast<int>(vertices.size())));
  if (result.second)
    stations.insert(make_pair(result.first->second, make_pair(cr, cs)));
  return result.first->second;
}

void print_path(int u, int w, char& cr)
{
  pair<int, int> s = stations[u];
  if (parents[u] == -1) {
    cr = s.first;
    printf("%c%c", cr, s.second);
  }
  else {
    print_path(parents[u], distances[u] - distances[parents[u]], cr);
    if (w) {
      if (s.first != cr) {
        cr = s.first;
        printf("=%c%c", cr, s.second);
      }
      else
        putchar(s.second);
    }
  }
}

int main()
{
  string s;
  getline(cin, s);
  istringstream iss(s);
  int nr_routes;
  iss >> nr_routes;
  vertices.clear();
  while (nr_routes--) {
    getline(cin, s);
    const char* p = s.c_str();
    char cr = *p++;
    int u = get_vertex(cr, *++p), su = u, v;
    for (p++; *p; p++) {
      if (*p == '=') { // ...hc=Bg=Cc=Abd...
        int ccr = *++p;
        v = get_vertex(ccr, *++p);
        if (v != su)
          edges[u].push_back(edge(v, 3)), edges[v].push_back(edge(u, 3));
        else
          edges[u].push_back(edge(v, 1)), edges[v].push_back(edge(u, 1));
      }
      else {
        v = get_vertex(cr, *p);
        edges[u].push_back(edge(v, 1)), edges[v].push_back(edge(u, 1));
        u = v;
      }
    }
  }
  int n = static_cast<int>(vertices.size());
  while (getline(cin, s) && s[0] != '#') {
    int start = get_vertex(s[0], s[1]), end = get_vertex(s[2], s[3]);
    int d = dijkstra_shortest_path(n, start, end);
    printf("%3d: ", d);
    char cr;
    print_path(end, -1, cr);
    putchar('\n');
  }
  return 0;
}