# 目次

• 目次
• 問題
• 解説
• 解答

# 問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_C

# 解説

隣接リストと優先度付きキューによるダイクストラ法

重み付き有向グラフのある頂点から各頂点への最短距離をもとめる.

各頂点は頂点<重み, ID>というペアで表す.

priority_queueのデフォルトの設定のままで重み順にソートさせるために、２つの工夫をしている.

1. IDではなく重みをペアの第一要素にしている.
2. デフォルトでは重みの大きい順にソートされてしまうので（最大ヒープ）、プッシュする際に重みに-1をかけて、ポップする時にもう一度-1をかけてもとに戻すことで最小ヒープにしている.

こうしないと、priority_queue に独自の比較オブジェクトを用意する必要がある.

グラフは、頂点数が多いので隣接行列ではなく隣接リストで表現する.

• 1. ２つのコンテナと１つの優先度付きキューを宣言する
  • 1. done[n] 各頂点の最短距離が確定したかいなか
  • 2. dist[n] 各頂点の今考えれる最短距離（実行完了までは確定とは限らない）
  • 3. priority_queue<Node> PQ 未確定でかつ原点からの距離が短い頂点順に並んだキュー
• 2. コンテナを初期化する
  • 1. done 全頂点false
  • 2. dist 原点自身0は距離0を、その他は∞
  • 3. PQ 原点0を距離0でプッシュする
• 3. キューが空になるまで以下を繰り返す
  • 1. キューの先頭uを取得し、未確定であれば次に進む
  • 2. 確定済みにする
  • 3. すべての隣接頂点vについて以下を実行する
    • 1. vが未確定であれば次に進む
    • 2. 原点からuまでのコストdist[u]とuからvへ距離weight(v)の和が今の所考えられていた原点からvまでの最小距離dist[v]よりも小さければ
      • 1. 最小距離を更新する
      • 2. キューにvのIDと原点からの最小距離をペアにしてプッシュする（この時距離をマイナスにするのを忘れずに）
• 4. distに原点0から各頂点への最短距離が確定されている

# 解答

// C++ 14
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <algorithm>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <unordered_map>
#include <math.h>

#define ll long long
#define Int int
#define loop(x, start, end) for(Int x = start; x < end; x++)
#define loopdown(x, start, end) for(int x = start; x > end; x--)
#define rep(n) for(int x = 0; x < n; x++)
#define span(a,x,y) a.begin()+x,a.begin()+y
#define span_all(a) a.begin(),a.end()
#define len(x) (x.size())
#define last(x) (*(x.end()-1))

using namespace std;

#define MAX_N 10000
#define W_INF (1 << 21)


typedef pair<Int, Int> Node;

#define make_node(v,c) (make_pair(v,c))
#define weight(n) (n.first)
#define vertex(n) (n.second)


void sssp(vector<Node> nodes[], Int n, Int dist[]) {
  bool done[n];
  priority_queue<Node> PQ;

  loop(i,0,n) done[i] = false, dist[i] = W_INF;
  dist[0] = 0, PQ.push(make_node(0, 0));

  while (!PQ.empty()) {
    Node node = PQ.top(); PQ.pop();
    Int u = vertex(node);
    if (done[u]) continue;
    done[u] = true;

    for (auto n_v: nodes[u]) {
      Int v = vertex(n_v);
      if (done[v]) continue;
      Int w = weight(n_v);

      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        PQ.push(make_node(dist[v] * (-1), v));
      }
    }
  }
}


int main(void) {
  Int n, k, v, c;
  cin >> n;
  vector<Node> nodes[n];
  Int dist[n];
  
  loop(u,0,n) {
    cin >> k >> k;
    loop(i,0,k) {
      cin >> v >> c;
      nodes[u].push_back(make_node(c, v));
    }
  }
  
  sssp(nodes, n, dist);
  loop(i,0,n) cout << i << " " << dist[i] << endl;
}