ダイクストラ法（Dijkstra法）は、グラフ上で単一始点（終点）の最短経路を効率的に求めるアルゴリズムです。
本記事ではC++で使えるダイクストラ法のライブラリを実装します。

※なお、今回のライブラリは Graph ライブラリが前提となっています。
以下リンクからコピペしてご使用ください↓
・グラフ構造体をC++で実装してみた

主な機能と計算量

名前	説明	計算量
`dijkstra<T>(g, starts)`	グラフ `g` の各頂点に対して、`starts` から各頂点への最短距離を計算	$O(E \ log \ V)$

実装したコード

//------ここにGraphライブラリ-------//
//                               //
//-------------------------------//


// 戻り値の配列retは、「ret[i] := starts から i への最短距離」となります
template<typename T = long long> // costの型
vector<T> dijkstra(Graph<T> &g, vector<int> starts){
    // {startsからの最短コスト、場所}の配列
    vector<T> ret(g.size_n(), T(100100100100100100));
    
    // 最短距離の短い順に処理するための優先度付きキュー
    using P = pair<T, int>;
    priority_queue<P, vector<P>, greater<P>> q; 
    
    //開始地点を初期化していく
    for(int start: starts){
        ret[start] = T(0);
        q.push({T(0), start});
    }
    
    //行けるところ全てを更新していく
    while(!q.empty()){
        //キューの中から、距離最小のものを取る
        int i = q.top().second;
        T c = q.top().first;
        q.pop();
        //もっといいスコアで計算されてるなら、無視
        if(ret[i] < c) continue;
        ret[i] = c;
        for(P &next: g.nexts(i)){
            int ni = next.second;
            int nc = next.first + c;
            //最小コストを更新できるときだけ更新
            if(ret[ni] <= nc) continue;
            ret[ni] = nc;
            q.push({nc, ni});
        }
    }
    
    return ret;
}

使用例

#include<bits/stdc++.h>
using namespace std;


//------ここにGraphライブラリ-------//
//                               //
//-------------------------------//


//--ここにDijkstraライブラリ--//
//                         //
//-------------------------//


int main(void){
    // グラフの作成
    Graph g(4);

    g.add_edge(10, 0, 1); //0 → 1：コスト10の辺を追加
    g.add_edge(10, 0, 2); //0 → 2：コスト10の辺を追加
    g.add_edge(15, 0, 3); //0 → 3：コスト15の辺を追加
    g.add_edge(1, 2, 3); //2 → 3：コスト1の辺を追加
    
    // 0から各頂点への最短距離を求める
    vector<long long> dijk = dijkstra(g, {0});
    cout << dijk[3] << endl; // 11
}

注意点・Tips

頂点番号は0-indexedで扱っています
コストの型 T には、long long、int、doubleなどが使えます
starts から辿り着けない頂点は、最短距離が100100100100100100となっています
dijkstra(g, {0,2,3}) とすれば、多点スタートも可能です
始点が一つであっても dijkstra(g, {0}) とする必要があることに注意してください

実際に使ってみる

AtCoder Beginner Contest 035 - D問題

#include <bits/stdc++.h>
using namespace std;


//------ここにGraphライブラリ-------//
//                               //
//-------------------------------//


//---ここにDijkstraライブラリ---//
//                           //
//---------------------------//


// グローバル変数
int N, M, T;
vector<int> A;

int main(void){
    // 入力
    cin >> N >> M >> T;
    A.resize(N);
    for(int i=0;i<N;i++) cin >> A[i];
    
    // 行きと帰りの最短経路を計算するため、辺を逆にしたグラフも作っておく
    Graph g(N);
    Graph ig(N);
    
    // グラフを構築
    for(int i=0;i<M;i++){
        int a, b, c;
        cin >> a >> b >> c;
        a--; // 0-indexedに変換
        b--; // 0-indexedに変換
        g.add_edge(c, a, b);
        ig.add_edge(c, b, a);
    }
    
    //各頂点までの往復の最短経路を計算
    vector<long long> dijk = dijkstra(g, {0});
    vector<long long> idijk = dijkstra(ig, {0});
    
    //各頂点に対して、最短で往復した場合に得られる最大利益を計算
    long long ans = 0;
    for(int i=0;i<N;i++){
        long long cost = dijk[i] + idijk[i];
        //そもそも往復できないなら無視
        if(cost > T) continue;
        ans = max(ans, (T-cost)*A[i]);
    }
    cout << ans << endl;
}

関連リンク