Dijkstra

struct Dijkstra {
  using elem = pair<ll, int>;
  const ll INF = 2e18;

  int vol;
  vector<ll> dup;
  vector<vector<elem>> adj;

  Dijkstra(int _vol) {
    vol = _vol + 1;
    dup.resize(vol, INF);
    adj.resize(vol);
  }

  void connect(int u, int v, ll w) {
    adj[u].push_back({w, v});
  }

  void run(int base) {
    priority_queue<elem, vector<elem>, greater<elem>> que;
    que.push({0, base});
    dup[base] = 0;

    while (!que.empty()) {
      auto [cw, id] = que.top(); que.pop();
      if (dup[id] < cw) continue;

      for (auto [w, nxt] : adj[id]) {
        if (dup[nxt] > cw + w) {
          dup[nxt] = cw + w;
          que.push({dup[nxt], nxt});
        }
      }
    }
  }
};

 

201224*

자료형 long long으로 변경

 

210204*

재작성

 

210712*

재작성