dijkstra

# -*- mode: snippet -*-
# name: dijkstra
# key: dijkstra
# --
using DistanceType = double;

const int MAX_V = 501 * 501;  // TODO
const DistanceType INF = INT_MAX;

struct Edge {
  int to;
  DistanceType cost;
};
typedef pair<DistanceType, int> P;  // firstは最短距離、secondは頂点の番号

int V;                  // 頂点数 TODO
vector<Edge> G[MAX_V];  // グラフ TODO
DistanceType d[MAX_V];  // 頂点sからの最短距離
int prev_[MAX_V];       // 最短路の直前の頂点

void dijkstra(int s) {
  priority_queue<P, vector<P>, greater<P>> que;
  fill(d, d + V, INF);
  fill(prev_, prev_ + V, -1);
  d[s] = 0;
  que.push(P(0, s));

  while (!que.empty()) {
    P p = que.top();
    que.pop();
    int v = p.second;
    if (d[v] < p.first)
      continue;
    for (int i = 0; i < (int)G[v].size(); i++) {
      Edge e = G[v][i];
      if (d[e.to] > d[v] + e.cost) {
        d[e.to] = d[v] + e.cost;
        prev_[e.to] = v;
        que.push(P(d[e.to], e.to));
      }
    }
  }
}

vector<int> get_path(int t) {
  vector<int> path;

  for (; t != -1; t = prev_[t]) {
    path.push_back(t);
  }
  reverse(path.begin(), path.end());
  return path;
}