graph.dij - ダイクストラ法

graph.dij.rs

type Costi64f64. 始点を s として, 各頂点までの最短コストの列を返す.

/// @algebra.hyper.rs
/// @algebra.total.rs

fn dij<Cost: Group + PartialOrd> (s: usize, neigh: &Vec<Vec<(usize, Cost)>>) -> Vec<Hyper<Cost>> {
    let n = neigh.len();
    let mut d: Vec<Hyper<Cost>> = vec![Inf; n];
    let mut q = std::collections::BinaryHeap::new();
    d[s] = Real(Cost::zero());
    q.push((Total(d[s]), s));
    while let Some((_, u)) = q.pop() {
        for &(v, cost) in neigh[u].iter() {
            if d[v] > d[u] + Real(cost) {
                d[v] = d[u] + Real(cost);
                q.push((Total(-d[v]), v));
            }
        }
    }
    d
}

graph.dij.cc

  • 入力;
    • using Cost = long long
    • 始点 s: int
    • コスト付き隣接リスト vector<vector<pair<int, Cost>>> &neigh
  • 出力
    • 各点までの最短コストの列 vector<Cost> d
#define inf (1e18)
using Cost = long long;

vector<Cost>
dij(int s, vector<vector<pair<int, Cost>>> &neigh) {
  const int n = neigh.size();
  vector<Cost> d(n, inf); d[s] = 0;
  priority_queue<pair<Cost, int>> q; q.push({0, s});
  while (not q.empty()) {
    int u = q.top().second; q.pop();
    for (auto pair: neigh[u]) {
      int v = pair.first;
      Cost c = pair.second;
      if (d[v] > d[u] + c) {
        d[v] = d[u] + c;
        q.push({ -d[v], v });
      }
    }
  }
  return d;
}

int main() {
  int n, m; cin >> n >> m;
  vector<vector<pair<int, Cost>>> neigh(n);
  rep (i, m) {
    int u, v; cin >> u >> v; --u; --v;
    Cost c; cin >> c;
    neigh[u].emplace_back(v, c);
    neigh[v].emplace_back(u, c);
  }

  auto result = dij(0, neigh);
  cout << result << endl;

  return 0;
}