ダイクストラ法

priority-queueを使って貪欲に「今選べる頂点の中で一番近い頂点」を選んでいくことで、単一始点最短経路を求める。

実質貪欲

理解しやすいイメージがある。偏見。

実装としては、

辺はstruct edge{ int to, cost; };でもつ

それぞれの頂点への最短経路をもつvector<int> dist(n)みたいなのを用意する

pair<int,int>は使いがちなのでtypedef pair<int,int> P; しておく

firstは最短距離、secondは頂点番号

priority_queue<P, vector<P>, greater<P> > que; を使う

「second番目の頂点への最短距離をfirstで置き換えました！」という意味（過去形ってのがポイント）