Dijkstra 法の実装例

はじめに

先日の　AtCoder Begineer Contest 362 の D 問題で問われていた Dijkstra 法の実装が上手くいかなかったため、いつでも振り返られるように忘備録として残す。

実装例

特にひねりのない基本問題であれば、★コスト計算する上で、カスタマイズの可能性あり★以下の部分を適切に処理することで対応できる場合が多いと感じた。

#include <stdio.h>
#include <stdlib.h>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;

// ----------------------------------------------------------------------

int main(void){
  int n, m;
  cin >> n >> m;
  vll a(n);
  for(int i = 0; i < n; i++) cin >> a[i];

  vector<vector<pair<int, ll>>> G(n);// <隣接する頂点番号, 辺の重み>
  for(int i = 0; i < m; i++) {
	int u, v;
    ll b;
    cin >> u >> v >> b;
    u--; v--;
    G[u].push_back({v, b});
    G[v].push_back({u, b});
  }

  vll dist(n, 2e18);// long long を想定した初期化

  int sv = 0; // 起点となる頂点番号
  dist[sv] = 0; // 起点そのものからの距離は、当然0

  using plli = pair<ll, int>; //現在地を表す。<スタート地点から距離(コスト), 現在地のindex>
  priority_queue<plli, vector<plli>, greater<plli>> que;
  que.push({0, sv});// 初回データは、起点となる頂点番号となる
  
  while(!que.empty()) {
    auto [d, v] = que.top();
    que.pop();
    if (d > dist[v]) // dist[v]: 現時点でのvまでの最速距離
      continue;
    for (ll i = 0; i < G[v].size(); i++) {
      auto [nv, cost] = G[v][i];
      // ここでコスト加算する。
      // ★コスト計算する上で、カスタマイズの可能性あり★
      ll nc = d + cost + a[nv];
      if (nc < dist[nv]) {
        dist[nv] = nc;
        que.push({dist[nv], nv});
      }
    }
  }

  for(int i = 1; i < n; i++) {
  	cout << dist[i] + a[0] << " ";
  }
}

終わりに

重みづけグラフの問題が出題されると、問題文を見るだけで敬遠しがちだったが、これでもう対策はバッチリだ☆

※追記(2024/10/04)

• 最小コストのパスを探索するとき、起点となる頂点番号を sv とすることで、柔軟に対応できるようにした。