#include <stdio.h>
#include <memory.h>
#include <vector>
using namespace std;

class node{
public:
 int pp;
 int data;
 bool operator > (node right)
 {
  return data > right.data;
 }
 bool operator < (node right)
 {
  return data < right.data;
 }
 bool operator >= (node right)
 {
  return data >= right.data;
 }
 bool operator <= (node right)
 {
  return data <= right.data;
 }
};

vector<node> list[501];
/*
Vector에 데이터를 넣어준다.

끝점과 가중치를 넣을 때는

node 임시변수; 를 만들고
임시변수.pp = 끝점
임시변수.data=가중치

로 대입한뒤 list[시작점].push_back(임시변수)로 하면 리스트가 만들어진다.
*/

int pos[501]; /* 정점의 힙 내부의 위치를 나타내는 배열 */

template <typename T>
inline void swaps(T &a, T &b) /* SWAP 함수 */
{
        T t = a;
        a = b;
        b = t;
}

template <typename T>

class min_heap{ /* Min_HEAP를 구현한 클래스이다. MIN HEAP는 다 알테니 생략. */
public: /* 사실 Priority_queue를 이용해도 되지만 클래스 예제와 힙 직접 구현 연습을 위해 직접 구현했다. */
 T data[501];
 int heapcnt;
 T ms;
 min_heap()
 {
  heapcnt=0;
 };

 /* Functions */

 void push(T v)
 {
  data[++heapcnt]=v;
  int p=heapcnt;
  while(1)
  {
   if(p==1)
    break;
   if(data[p/2]>data[p])
   {
    swaps(pos[data[p/2].pp],pos[data[p].pp]);
    swaps(data[p/2],data[p]);
    //swap(1,2);
    p /= 2;
   }
   else
    break;
   
  }
 }

 T top()
 {
  return data[1];
 }

 void pop()
 {
  if(heapcnt==0) return;
  int p=1;
  data[1]=data[heapcnt];
  data[heapcnt]=ms;
  heapcnt--;
  while(1)
  {
   if(heapcnt/2<p) break;
   if(p*2>heapcnt) continue;
   if(p*2+1>heapcnt)
   {
    if(data[p*2]<data[p])
    {
     swaps(pos[data[p*2].pp],pos[data[p].pp]);
     swaps(data[p*2],data[p]);
    }
    break;
   }
   if(data[p*2] <= data[p*2+1] && data[p*2] < data[p])
   {
    swaps(pos[data[p*2].pp],pos[data[p].pp]);
    swaps(data[p*2],data[p]);
    p *= 2;
   }
   else if(data[p*2] > data[p*2+1] && data[p*2+1] < data[p])
   {
    swaps(pos[data[p*2+1].pp],pos[data[p].pp]);
    swaps(data[p*2+1],data[p]);
    p=p*2+1;
   }
   else
   {
    break;
   }
   
  }
 }

 bool empty()
 {
  if(heapcnt==0)
   return true;
  return false;
 }

 int size()
 {
  return heapcnt;
 }

 void refresh(int p)
 {
  while(1)
  {
   if(heapcnt/2<p) break;
   if(p*2>heapcnt) continue;
   if(p*2+1>heapcnt)
   {
    if(data[p*2]<data[p])
    {
     swaps(pos[data[p*2].pp],pos[data[p].pp]);
     swaps(data[p*2],data[p]);
    
     
    }
    break;
   }
   if(data[p*2] <= data[p*2+1] && data[p*2] < data[p])
   {
    swaps(pos[data[p*2].pp],pos[data[p].pp]);
    swaps(data[p*2],data[p]);
    
    p *= 2;
   }
   else if(data[p*2] > data[p*2+1] && data[p*2+1] < data[p])
   {
    swaps(pos[data[p*2+1].pp],pos[data[p].pp]);
    swaps(data[p*2+1],data[p]);
    
    p=p*2+1;
   }
   else
   {
    break;
   }
   
  }
 }

 /* End of Functions */
};

/*
여기까지가 힙 클래스. 사실 이 코드가 200줄 이상인 이유는 힙 클래스 때문이다 -_-;

힙클래스를 제외하고 쓸모없는 부분을 제외한다면 실제로 50줄 이내

*/

int dist[501][501]; // 최단거리를 저장하는 배열이다.

void dijkstra(int s) //E log V Dijkstra 부분이다. dijkstra(시작점)으로 호출을 하면 dist[시작점][끝점] 에 최단거리가 저장된다.
{
 int i;
 min_heap<node> heap; //MIN_HEAP
 bool chk[501]; //체크 배열
 
 int j;
 for(i=1;i<=500;i++) //배열 초기화
 {
  dist[s][i]=0;
  pos[i]=0;
  chk[i]=0;
 }
 node tmp; //데이터를 push / pop하기 위한 임시 변수
 for(i=0;i<list[s].size();i++) //시작점에서 갈수있는곳을 우선 힙에 저장.
 {
  tmp=list[s][i];
  heap.push(tmp);
  pos[tmp.pp]=heap.size();
  chk[tmp.pp]=true;
 }
 for(i=1;i<=n;i++)
 {
  if(chk[i]==0 && i != s)
  {
   tmp.pp=i;
   tmp.data=1000000001;
   heap.push(tmp);
   pos[i]=heap.size();
  }
 }
 node tmp2; // 위의 node tmp와 같음.
 for(i=1;i<n;i++)

 {
  tmp=heap.top();
  pos[heap.data[heap.size()].pp]=1;
  pos[1]=pos[heap.size()];
  heap.pop();
  dist[s][tmp.pp]=tmp.data;
  for(j=0;j<list[tmp.pp].size();j++)
  {
   tmp2=list[tmp.pp][j];
   if(pos[tmp2.pp] > 0 && heap.data[pos[tmp2.pp]].data > tmp.data + tmp2.data)
   {
    heap.data[pos[tmp2.pp]].data=tmp.data+tmp2.data;
    heap.refresh(pos[tmp2.pp]);
   }
  }
 }
}