record

#include <stdio.h>

int num = 6;
// 무한을 표현하려고 선언 
int INF = 1000000000;

// 전체 그래프 초기화 
int a[6][6] = {
	{0, 2, 5, 1, INF, INF},
	{2, 2, 5, 1, INF, INF},
	{5, 3, 0, 3, 1, 5},
	{1, 2, 3, 0, 1, INF},
	{INF, INF, 1, 1, 0, 2},
	{INF, INF, 5, INF, 2, 0},
};
 
bool v[6]; // 방문한 노드인지 확인 배열 
int d[6];  // 최단거리   

// 가장 최소 거리를 가지는 정점을 반환한다. 
// 시간 복잡도 O(N)
int getSmallIndex(){
	int min = INF;
	int index = 0;
	
	for(int i = 0; i < num; i++) {
		if(d[i] < min && !v[i]){
			min = d[i];
			index = i;
		}
	}
	
	return index;
}
void dijkstra(int start){
	for(int i = 0; i < num; i++){
		d[i] = a[start][i];
		
	}
	
	v[start] = true;
	for(int i =0; i < num - 2; i++){
		int current = getSmallIndex();
		v[current] = true;
        // 시간 복잡도 O(N)
		for(int j = 0; j < 6; j++){
			// 방문하지 않았다면 
			if(!v[j]){
				// 현재 보고있는 노드의 최소비용에서 해당 노드를 거처서 그 노드의 인접한 노드로 가는 비용을 더한 값
				//  현재 인접한 노드로 가는 최소 비용보다 더 작다면 갱신해준다. 
				if( d[current] + a[current][j] < d[j] ) {
					d[j] = d[current] + a[current][j];
				}
			}	
		}
	}
}
 
int main(void) {
	
	dijkstra(0);
	
	for(int i = 0; i < num; i++) {
		printf("%d ", d[i]);
	} 
	return 0;
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int num = 6;
// 무한을 표현하려고 선언 
int INF = 1000000000;



vector<pair<int, int> > a[7]; // 간선 정보 
int d[7];  // 최단거리 (최소 비용)

void dijkstra(int start){
	d[start] = 0;
	// priority_queue는 기본적으로 더 큰값을 기준으로 최상단 노드를 만든다. (최대 힙)
	priority_queue<pair<int, int> > pq; // 힙 구조 입니다.
	pq.push(make_pair(start, 0));
	// 가까운 순서대로 처리하므로 큐를 사용한다.
	// priority_queue 가 비어있지 않다면 하나씩 꺼낸다. 
	while(!pq.empty()) {
		int current = pq.top().first;
		// priority_queue가 최대힙 구조로 형성이 되기때문에 
		// 짧은 것이 먼저 오도록 음수화(-) 한다.
		int distance = -pq.top().second;
		pq.pop();
		// 최단 거리가 아닌 경우 스킵
		if(d[current] < distance) continue;
		for(int i = 0; i < a[current].size(); i++) {
			// 선택된 노드의 인접 노드
			int next = a[current][i].first;
			// 선택된 노드 거쳐서 인접 노드로 가는 비용
			int nextDistance = distance + a[current][i].second;
			// 기존의 최소 비용보다 더 저렴하다면 교체한다.
			if(nextDistance < d[next]) {
				d[next] = nextDistance;
				// nextDistance를 음수로 저장하는 이유 힙이 최대 힙 구조로 형성되기 때문이다.
				// 더 작은 값이 윗 쪽으로 가게 만들기 위해서이다. 
				pq.push(make_pair(next, -nextDistance));
			}
		}
	}
}
 
int main(void) {
	// 연결되지 않은 경우 비용은 무한
	for(int i = 1; i <= num; i++) {
		d[i] = INF; 
	} 
	
	a[1].push_back(make_pair(2, 2));
	a[1].push_back(make_pair(3, 5));
	a[1].push_back(make_pair(4, 1));
	
	a[2].push_back(make_pair(1, 2));
	a[2].push_back(make_pair(3, 3));
	a[2].push_back(make_pair(4, 2));
	
	
	a[3].push_back(make_pair(1, 5));
	a[3].push_back(make_pair(2, 3));
	a[3].push_back(make_pair(4, 3));
	a[3].push_back(make_pair(5, 1));
	a[3].push_back(make_pair(6, 5));
	
	a[4].push_back(make_pair(1, 1));
	a[4].push_back(make_pair(2, 2));
	a[4].push_back(make_pair(3, 3));
	a[4].push_back(make_pair(5, 1));
	
	a[5].push_back(make_pair(3, 1));
	a[5].push_back(make_pair(4, 1));
	a[5].push_back(make_pair(6, 2));
	
	a[6].push_back(make_pair(3, 5));
	a[6].push_back(make_pair(5, 2));
	
	
	dijkstra(1);
	
	// 결과 출력 
	for(int i = 1; i <= num; i++) {
		printf("%d ", d[i]);
	} 
	return 0;
}