using System;
using System.Collections.Generic;
using System.Linq;
// Q041 単一始点最短距離1 https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_12_B&lang=jp
class Program
{
static string InputPattern = "InputX";
static List<string> GetInputList()
{
var WillReturn = new List<string>();
if (InputPattern == "Input1") {
WillReturn.Add("5");
WillReturn.Add("0 3 2 3 3 1 1 2");
WillReturn.Add("1 2 0 2 3 4");
WillReturn.Add("2 3 0 3 3 1 4 1");
WillReturn.Add("3 4 2 1 0 1 1 4 4 3");
WillReturn.Add("4 2 2 1 3 3");
//0 0
//1 2
//2 2
//3 1
//4 3
}
else {
string wkStr;
while ((wkStr = Console.ReadLine()) != null) WillReturn.Add(wkStr);
}
return WillReturn;
}
struct EdgeInfoDef
{
internal int ToNode;
internal int Cost;
}
// 隣接リスト
static Dictionary<int, EdgeInfoDef[]> mEdgeArrDict = new Dictionary<int, EdgeInfoDef[]>();
static void Main()
{
List<string> InputList = GetInputList();
int N = int.Parse(InputList[0]);
int[] wkArr = { };
Action<string> SplitAct = pStr =>
wkArr = pStr.Split(' ').Select(X => int.Parse(X)).ToArray();
foreach (string EachStr in InputList.Skip(1)) {
SplitAct(EachStr);
int NodeID = wkArr[0];
var EdgeInfoList = new List<EdgeInfoDef>();
for (int I = 2; I <= wkArr.GetUpperBound(0); I += 2) {
EdgeInfoDef WillAdd;
WillAdd.ToNode = wkArr[I];
WillAdd.Cost = wkArr[I + 1];
EdgeInfoList.Add(WillAdd);
}
mEdgeArrDict[NodeID] = EdgeInfoList.ToArray();
}
Dijkstra();
}
//ダイクストラ法で、各ノードまでの最短距離を求める
static void Dijkstra()
{
var InsPQueue = new PQueue();
// 距離合計[確定ノード]なDict
var KakuteiNodeDict = new Dictionary<int, int>();
KakuteiNodeDict.Add(0, 0);
//Enqueue処理
Action<int> EnqueueAct = pFromNode =>
{
foreach (EdgeInfoDef EachEdge in mEdgeArrDict[pFromNode]) {
// 確定ノードならContinue
if (KakuteiNodeDict.ContainsKey(EachEdge.ToNode)) continue;
int wkSumCost = KakuteiNodeDict[pFromNode] + EachEdge.Cost;
PQueue.PQueueJyoutaiDef WillEnqueue;
WillEnqueue.Node = EachEdge.ToNode;
WillEnqueue.SumCost = wkSumCost;
InsPQueue.Enqueue(WillEnqueue);
}
};
EnqueueAct(0);
while (InsPQueue.IsEmpty() == false) {
PQueue.PQueueJyoutaiDef Dequeued = InsPQueue.Dequeue();
//確定ノードならContinue
if (KakuteiNodeDict.ContainsKey(Dequeued.Node)) continue;
KakuteiNodeDict.Add(Dequeued.Node, Dequeued.SumCost);
EnqueueAct(Dequeued.Node);
}
foreach (var EachPair in KakuteiNodeDict.OrderBy(X => X.Key)) {
Console.WriteLine("{0} {1}", EachPair.Key, EachPair.Value);
}
}
}
#region PQueue
// 優先度付きキュー
internal class PQueue
{
internal struct PQueueJyoutaiDef
{
internal int Node;
internal int SumCost;
}
private Dictionary<int, PQueueJyoutaiDef> mHeapDict = new Dictionary<int, PQueueJyoutaiDef>();
internal bool IsEmpty()
{
return mHeapDict.Count == 0;
}
// エンキュー処理
internal void Enqueue(PQueueJyoutaiDef pAddJyoutai)
{
int CurrNode = 1 + mHeapDict.Count;
mHeapDict[CurrNode] = pAddJyoutai;
while (1 < CurrNode && mHeapDict[CurrNode / 2].SumCost > mHeapDict[CurrNode].SumCost) {
PQueueJyoutaiDef Swap = mHeapDict[CurrNode];
mHeapDict[CurrNode] = mHeapDict[CurrNode / 2];
mHeapDict[CurrNode / 2] = Swap;
CurrNode /= 2;
}
}
// デキュー処理
internal PQueueJyoutaiDef Dequeue()
{
PQueueJyoutaiDef TopNode = mHeapDict[1];
int LastNode = mHeapDict.Count;
mHeapDict[1] = mHeapDict[LastNode];
mHeapDict.Remove(LastNode);
MinHeapify(1);
return TopNode;
}
// 根ノードを指定し、根から葉へヒープ構築
private void MinHeapify(int pRootNode)
{
if (mHeapDict.Count <= 1) {
return;
}
int Left = pRootNode * 2;
int Right = pRootNode * 2 + 1;
// 左の子、自分、右の子で値が最小のノードを選ぶ
int Smallest = mHeapDict[pRootNode].SumCost;
int SmallestNode = pRootNode;
if (mHeapDict.ContainsKey(Left) && mHeapDict[Left].SumCost < Smallest) {
Smallest = mHeapDict[Left].SumCost;
SmallestNode = Left;
}
if (mHeapDict.ContainsKey(Right) && mHeapDict[Right].SumCost < Smallest) {
Smallest = mHeapDict[Right].SumCost;
SmallestNode = Right;
}
// 子ノードのほうが大きい場合
if (SmallestNode != pRootNode) {
PQueueJyoutaiDef Swap = mHeapDict[SmallestNode];
mHeapDict[SmallestNode] = mHeapDict[pRootNode];
mHeapDict[pRootNode] = Swap;
// 再帰的に呼び出し
MinHeapify(SmallestNode);
}
}
}
#endregion