ダイクストラ

// priority_queue を使う場合と使わない場合がある。
// 計算量が違うので使い分けること。
// 負のコストがある場合はベルマン・フォードを使う。

// priority_queue を使わない場合。計算量O(V^2)｡
// グラフにおいて start 地点から i 地点への最小移動コストを求める。
// m[i][j] に i から j へ移動するコストを入れる。
// 双方向リストの場合 m[i][j] と m[j][i] に値を入れること。
// たどり着けない場合には INF を入れる。
// MAX_V に最大のノード数を設定。INF は十分大きな値。
// m[i][j] をセットし dijk(start,V)で呼ぶ。
// start はスタート地点、V はノードの数。
// 答えは mn[i] に存在する。
// 負のコストは禁止。

#define MAX_V 50
#define INF 1000000000

int m[MAX_V][MAX_V];
int mn[MAX_V];
int dijflag[MAX_V];

void dijk(int start, int V){
  for(int i = 0; i < MAX_V; i++)mn[i] = INF;
  for(int i = 0; i < MAX_V; i++)dijflag[i] = 0;
  mn[start] = 0;
  for(;;){
    int v = -1;
    for(int i = 0; i < V; i++){
      if(dijflag[i] == 0){
        if(v == -1){
          v = i;
        }
        else{
          if(mn[i] < mn[v]){
            v = i;
          }
        }
      }
    }
    if(v == -1)break;
    dijflag[v] = 1;
    for(int i = 0; i < V; i++){
      if(mn[i] > mn[v] + m[v][i]){
        mn[i] = mn[v] + m[v][i];
      }
    }
  }
}

// priority_queue を使う場合。計算量O(Elog(V))｡
// グラフにおいて start 地点から i 地点への最小移動コストを求める。
// ae(from,to,cost)でエッヂを追加。
// MAX_V に最大のノード数を設定。INF は十分大きな値。
// すべてのエッヂを追加し dijk(start,V)を呼ぶ。
// start はスタート地点、V はノードの数。
// 答えは mn[i] に存在する。
// 負のコストは禁止。

#define MAX_V 200002
#define INF 1000000000

struct edge{int to, cost;};
typedef pair<int,int> P;

vector<edge> G[MAX_V];
int mn[MAX_V];

void ae(int from, int to, int cost){
  edge e = {to,cost};
  G[from].push_back(e);
}

void dijk(int start, int V){
  priority_queue<P, vector<P>, greater<P> > que;
  for(int i = 0; i < V; i++)mn[i] = INF;
  mn[start] = 0;
  que.push(P(0,start));
  while(!que.empty()){
    P p = que.top(); que.pop();
    int v = p.second;
    if(mn[v]<p.first)continue;
    for(int i = 0; i < G[v].size(); i++){
      edge e = G[v][i];
      if(mn[e.to] > mn[v]+e.cost){
        mn[e.to] = mn[v]+e.cost;
        que.push(P(mn[e.to],e.to));
      }
    }
  }
}

// 値を持つ場合

#define MAX_V 50
#define MAX_STATE 100
#define INF 1000000000

struct edge{int to, cost;};
#define P pair<int,int>
#define Q pair<int,pair<int,int> >

vector<edge> G[MAX_V];
int mn[MAX_V][MAX_STATE];

void ae(int from, int to, int cost){
  edge e = {to,cost};
  G[from].push_back(e);
}

void dijk(int start, int V){
  priority_queue<Q,vector<Q>,greater<Q> > que;
  mn[start][0] = 0;
  que.push(Q(0,P(start,0)));
  while(!que.empty()){
    Q node = que.top();
    que.pop();
    int num = node.se.fi;
    int state = node.se.se;
    if(mn[num][state]<node.fi)continue;
    rep(i,0,v[num].sz){
      edge e = v[num][i];
      if(mn[e.to][state]>mn[num][state]+e.cost){
        mn[e.to][state] = mn[num][state]+e.cost;
        que.push(Q(mn[e.to][state],P(e.to,state)));
      }
    }
  }
}