UVa 10269 - Adventure of Super Mario

Accepted date: 2016-04-24
Run Time: 0.000
Ranking (as of 2016-04-24): 6 out of 642
Language: C++

/*
  UVa 10269 - Adventure of Super Mario

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

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

const int A_max = 50, B_max = 50, n_max = A_max + B_max, L_max = 500, K_max = 10;

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

int matrix[n_max + 1][n_max + 1];
bool visited[n_max + 1], dvisited[n_max + 1][K_max + 1];
vector<edge> edges[n_max + 1];
int distances[n_max + 1][K_max + 1];
  // distances[i][j] is the min. time to vertex i using super-runs j times

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

int main()
{
  int T;
  scanf("%d", &T);
  while (T--) {
    int A, B, M, L, K;
    scanf("%d %d %d %d %d", &A, &B, &M, &L, &K);
    int n = A + B;
    for (int i = 1; i <= n; i++) {
      edges[i].clear();
      for (int j = 1; j <= n; j++)
        matrix[i][j] = numeric_limits<int>::max();
      for (int j = 0; j <= K; j++) {
        dvisited[i][j] = false;
        distances[i][j] = numeric_limits<int>::max();
      }
    }
    while (M--) {
      int Xi, Yi, Li;
      scanf("%d %d %d", &Xi, &Yi, &Li);
      matrix[Xi][Yi] = matrix[Yi][Xi] = Li;
      edges[Xi].push_back(edge(Yi, Li));
      edges[Yi].push_back(edge(Xi, Li));
    }

    // apply the Floyd-Warshall algorithm
    for (int k = 1; k <= A; k++)
      for (int i = 1; i <= n; i++)
        if (matrix[i][k] != numeric_limits<int>::max())
          for (int j = 1; j <= n; j++)
          if (matrix[k][j] != numeric_limits<int>::max())
            matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);

    // add the edges where super-running can be used
    for (int i = 1; i <= n - 1; i++)
      for (int j = i + 1; j <= n; j++)
        if (matrix[i][j] <= L) {
#ifdef DEBUG
          printf("s %d %d %d\n", i, j, matrix[i][j]);
#endif
          edges[i].push_back(edge(j, 0));
          edges[j].push_back(edge(i, 0));
        }

    // apply the Dijkstra's shortest path algorithm
    set<pair<int, int>, distance_comparator> pq; // priority queue
    distances[n][0] = 0;
    pq.insert(make_pair(n, 0));
    int min_t = numeric_limits<int>::max();
    while(!pq.empty()) {
      pair<int, int> p = *pq.begin();
      pq.erase(pq.begin());
      int u = p.first, k = p.second, t = distances[u][k];
      dvisited[u][k] = true;
#ifdef DEBUG
      printf("%d %d %d\n", u, k, t);
#endif
      if (u == 1) {
        min_t = t;
        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 (w && !dvisited[v][k] && t + w < distances[v][k]) {
          // a walk edge
          pair<int, int> q = make_pair(v, k);
          pq.erase(q);
          distances[v][k] = t + w;
#ifdef DEBUG
          printf("  %d %d %d\n", v, k, distances[v][k]);
#endif
          pq.insert(q);
        }
        if (!w && k < K && !dvisited[v][k + 1] && t < distances[v][k + 1]) {
          // a super-running edge
          pair<int, int> q = make_pair(v, k + 1);
          pq.erase(q);
          distances[v][k + 1] = t;
#ifdef DEBUG
          printf("  %d %d %d\n", v, k + 1, distances[v][k + 1]);
#endif
          pq.insert(q);
        }
      }
    }
    printf("%d\n", min_t);
  }
  return 0;
}