dijkstra.cpp

#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#include <unordered_map>
using namespace std;

template <typename Key, typename Value, typename Comp=std::greater<Value>>
class priorty_queue {
public:
  priorty_queue() {}
  bool empty() const {
    return data.empty();
  }
  const pair<Key, Value>& top() const {
    return data.front();
  }
  pair<Key, Value>& top() {
    return data.front();
  }
  pair<Key, Value> pop() {
    auto top = data.front();
    index.erase(top.first);
    data.front() = data.back();
    data.pop_back();
    if(!data.empty()) push_down(0);
    return top;
  }
  int push(const Key& key, const Value& value) {
    data.push_back(make_pair(key, value));
    int cur = data.size()-1;
    index[key] = cur;
    cur = push_up(cur);
    return cur;
  }
  void update(const Key& key, const Value& value) {
    auto it = index.find(key);
    if(it == index.end()) {
      cerr << "key = " << key << endl;
      throw std::out_of_range("The key value pair is not in priority queue!");
    } else {
      int cur = it->second;
      data[cur].second = value;
      push_up(cur);
      push_down(cur);
    }
  }

  template <typename KT, typename VT, typename CT>
  friend ostream& operator<<(ostream& os, const priorty_queue<KT, VT, CT>& Q);

protected:
  //    0
  //  1   2
  // 3 4 5 6
  int parent(int x) {
    if(x == 0) return -1;
    else return (x-1) >> 1;
  }

  int left_child(int x) {
    return (x << 1) + 1;
  }

  int right_child(int x) {
    return (x << 1) + 2;
  }

  void swap(int a, int b) {
    index[data[a].first] = b;
    index[data[b].first] = a;
    std::swap(data[a], data[b]);
  }

  int push_up(int cur) {
    Comp comparer;
    int p = parent(cur);
    while(p >= 0 && comparer(data[p].second, data[cur].second)) {
      swap(p, cur);
      cur = p;
      p = parent(cur);
    }
    return cur;
  }

  int push_down(int cur) {
    Comp comparer;
    while(true) {
      auto min_idx = cur;
      int left_child_idx = left_child(cur);
      if(left_child_idx < data.size()) {
        min_idx = comparer(data[min_idx].second, data[left_child_idx].second)?left_child_idx:min_idx;
      }
      int right_child_idx = right_child(cur);
      if(right_child_idx < data.size()) {
        min_idx = comparer(data[min_idx].second, data[right_child_idx].second)?right_child_idx:min_idx;
      }

      if(min_idx > cur) {
        swap(cur, min_idx);
        cur = min_idx;
      } else break;
    }
    return cur;
  }

private:
  vector<pair<Key, Value>> data;
  unordered_map<Key, int> index;
};

template <typename Key, typename Value, typename Comp>
ostream& operator<<(ostream& os, const priorty_queue<Key, Value, Comp>& Q) {
  for(auto& it : Q.data) {
    os << "(" << it.first << ": " << it.second << ") ";
  }
  os << endl;
  for(auto& it : Q.index) {
    os << it.first << ": " << it.second << ' ';
  }
  return os;
}

vector<int> dijkstra(int s, const vector<vector<pair<int, int>>>& e) {
  const int n = e.size();
  vector<int> d(n, INT_MAX);
  d[s] = 0;
  priorty_queue<int, int> Q;
  for(int i=0;i<n;++i) {
    Q.push(i, d[i]);
  }

  while(!Q.empty()) {
    auto cur = Q.pop();
    int u = cur.first;
    int v, w_uv;
    for(auto it : e[u]) {
      tie(v, w_uv) = it;
      if(d[u] < INT_MAX) {
        int alt = d[u] + w_uv;
        if(alt < d[v]) {
          d[v] = alt;
          Q.update(v, d[v]);
        }
      }
    }
  }
  return d;
}
int main(int argc, char **argv) {
  int T;
  cin >> T;
  while(T-->0) {
    int N, M;
    cin >> N >> M;
    //cerr << N << ' ' << M << endl;
    vector<vector<pair<int, int>>> e(N, vector<pair<int, int>>());
    for(int i=0;i<M;++i) {
      int s, t, w;
      cin >> s >> t >> w; --s; --t;
      e[s].push_back(make_pair(t, w));
      e[t].push_back(make_pair(s, w));
    }

    int S;
    cin >> S; --S;
    auto d = dijkstra(S, e);
    for(int i=0;i<d.size();++i) {
      if(i!=S) {
        if(d[i] == INT_MAX) cout << -1 << ' ';
        else cout << d[i] << ' ';
      }
    }
    cout << endl;
  }
  return 0;
}