【自分用メモ】ダイクストラ法
ダイクストラ法のコード
ダイクストラ法とは…
グラフのある頂点から他の頂点への最短距離を求めるときの方法
参考書
ダイクストラ法 - 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)); } } } }