POJ 1062 - 昂贵的聘礼: typical Dijkstra algorithm problem

gift_min_price.cc

#include <cstdio>
#include <iostream>
#include <utility>
#include <vector>

using namespace std;

/*
   Note all operations on arrays/vectors start from index 1.
*/

const int kMaxNodeNumber = 101;
const int kInf = ~(1 << 31);

// Use Dijkstra's algorithm to calculate the distances.
int CalculateMinDistance(const vector<vector<int> >& edges,
                         const vector<int>& prices,
                         const vector<int>& levels,
                         int node_num,
                         int level_diff_limit) {
  static bool visited[kMaxNodeNumber];
  // Reset the flags.
  for (int i = 0; i < kMaxNodeNumber; ++i) {
    visited[i] = false;
  }

  vector<int> dist(node_num + 1, kInf);
  int src_level = levels[1];
  dist[1] = prices[1];

  // Iterations of `node_num` times.
  for (int i = 0; i < node_num; ++i) {
    // Find the node with min distance.
    int min_dist = kInf, min_node;
    for (int node = 1; node <= node_num; ++node) {
      if (!visited[node] && dist[node] < min_dist) {
        min_dist = dist[node];
        min_node = node;
      }
    }
    // Mark as visited.
    visited[min_node] = true;
    int src = min_node;
    // Traverse its edges and update the distance.
    for (int neighbor = 1; neighbor <= node_num; ++neighbor) {
      // Note the level must be lay in range.
      if (edges[src][neighbor] != kInf &&
          levels[neighbor] >= src_level - level_diff_limit &&
          levels[neighbor] <= src_level + level_diff_limit) {
        int new_dist = dist[src] - prices[src] +
                       edges[src][neighbor] + prices[neighbor];
        if (new_dist < dist[neighbor]) {
          dist[neighbor] = new_dist;
        }
      }
    }
  }
  int min_dist = kInf;
  for (int i = 1; i <= node_num; ++i)
    if (dist[i] < min_dist)
      min_dist = dist[i];

  return min_dist;
}

int main() {
  int node_num, level_diff_limit;
  // Note `node_num` should be less than 101.
  cin >> level_diff_limit >> node_num;

  // Prices for each node.
  vector<int> prices(node_num + 1, 0);
  // Levels, indicating status of the owner.
  vector<int> levels(node_num + 1, 0);
  // Edges, record the discounted prices. Init to inf.
  vector<vector<int> > edges(node_num + 1, vector<int>(node_num + 1, kInf));

  for (int src = 1; src <= node_num; ++src) {
    int neighbor_num;
    cin >> prices[src] >> levels[src] >> neighbor_num;

    for (int j = 0; j < neighbor_num; ++j) {
      int dest, discounted_price;
      cin >> dest >> discounted_price;
      edges[src][dest] = discounted_price;
    }
  }

  int min_price = CalculateMinDistance(
    edges, prices, levels, node_num, level_diff_limit);
  cout << min_price << endl;

  return 0;
}