読者です 読者をやめる 読者になる 読者になる

プロコン初心者日記

解いたプロコンの問題を保存しておくためのブログ

【自分用メモ】ダイクストラ法

ダイクストラ法のコード

ダイクストラ法とは…
グラフのある頂点から他の頂点への最短距離を求めるときの方法

参考書

プログラミングコンテストチャレンジブック [第2版]

ダイクストラ法 - Wikipediaのgifがわかりやすい

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
using namespace std;

#define ll         long long
#define PI         acos(-1.0)
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)

#define INF 99999999
#define MAX_E 1000
#define MAX_V 1000

//ダイクストラ法 using queue

//頂点の数
int V;
//次の頂点、次の頂点へのコスト
struct edge{ int to, cost; };

//頂点iと繋がっている頂点の情報
//G[i][頂点iと繋がっている頂点の個数]
vector<edge> G[MAX_V];

//始点からのコスト、頂点番号
//priority_queueで並び変えるためにpair
typedef pair<int, int> P;

//始点sからのコスト
int dijkstra(int s){
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+V, INF);
    d[0] = 0;
    que.push(P(0, s));

    while(!que.empty()){
        P p = que.top();que.pop();
        //頂点
        int v = p.second;
        //すでに小さくなっていたらcontinue;
        if(d[v] < p.first) continue;

        //vと繋がっている頂点についてコストが下がるかどうかを調べる
        FOR(i, 0, G[v].size()){
            edge e = G[v][i];
            if(d[e.to] > d[v] + e.cost){
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}