graph.dij

graph.dij.rs

use std::collections::BinaryHeap;

type Cost = i64;
const MaxCost: Cost = 1_000_000_000_000_000;

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

fn main() {

    let mut sc = Scanner::new();

    let n: usize = sc.cin(); // nodes
    let m: usize = sc.cin(); // edges
    let mut neigh = vec![vec![]; n];
    for _ in 0..m {
        let u = sc.cin::<usize>() - 1;
        let v = sc.cin::<usize>() - 1;
        let c: Cost = sc.cin();
        neigh[u].push((v, c));
        neigh[v].push((u, c));
    }

    let d = dij(0, &neigh);
    trace!(d);

}

graph.dij.cc

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