Dijkstra

1
auto res = dijkstra(g,s);

1
vector<int> dijkstra(DirectedGraph &_g,int s) {
2
  vector<int> d(_g.n, INF);
3
  priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
4
  d[s] = 0;
5
  que.push(make_pair(0, s));
6
  while (!que.empty()) {
7
    pair<int, int> p = que.top();
8
    que.pop();
9
    int v = p.second;
10
    if (d[v] < p.first)
11
      continue;
12
    for (auto e : _g.g[v]) {
13
      if (d[e.to] > d[v] + e.cost) {
14
        d[e.to] = d[v] + e.cost;
15
        que.push(make_pair(d[e.to], e.to));
16
      }
17
    }
18
  }
19
  return d;
20
}