//
//  dijkstra.cpp
//  console2
//

/* priority_queue 큐를 이용하여 Dijkstra 최소 비용 거리(경로) 구하기
 */

#include <vector>
#include <queue>
#include <iostream>
#include <fstream>
#include <sstream>

#include <stdio.h>
#include <math.h>

using namespace std;

// 무한대값 정의
#define INF 10000000

int NO_PARENT = -1;

// pair<int, int> 에 대한 intPair 타입 정의
typedef pair<int, int> intPair;

void printPath(int currentVertex, vector<int> parents)
{
    if ( currentVertex == NO_PARENT )
    {
        return;
    }
    printPath(parents[currentVertex], parents);
    cout << currentVertex << " ";
}

// 인접한 두지점(노드)의 경로 비용(거리 값) 추가
void add_node(vector <pair<int, int> > adj_nodes[], int a, int b, int dist)
{
    // s 지점(노드)에 e 지점(노드)과 거리 값 추가
    adj_nodes[a].push_back(make_pair(b, dist));
    // e 지점(노드)에 s 지점(노드)과 거리 값 추가
    adj_nodes[b].push_back(make_pair(a, dist));
}

// 최단 거리 (최소 비용) 경로를 시작 지점으로부터 구함
// Prints shortest paths from start to all other vertices
int get_shortest_distance(vector<pair<int,int> > adj_nodes[], size_t nodes_num,
                           int start, int end)
{
    // 전처리중인 정점을 저장할 priority queue 를 만든다
    priority_queue< intPair, vector <intPair> , greater<intPair> > pq;
  
    // 거리에 대한 정점을 만들고 최대 거리값 infinite(INF)으로 초기화
    vector<int> dist(nodes_num, INF);
  
    // 처음 시작 노드는 거리가 0 이므로 0으로 설정해서 넣는다(추가)
    pq.push(make_pair(start, 0));
    dist[start] = 0;
  
    // Parent array to store shortest
    // path tree
    vector<int> parents(nodes_num);
 
    // The starting vertex does not
    // have a parent
    for ( int i = 0; i < nodes_num; i++ )
    {
        parents[i] = NO_PARENT;
    }

    // priority queue 가 없을 때까지(모든 노드에 대한 거리가 설정될 때까지) 반복
    while ( !pq.empty() )
    {
        // priority queue 첫번째 정점 노드는 최소 거리의 정점이며,
        // priority queue 에서 추출한다.
        // pair 에서 첫번째(first)가 정점의 이름(경로 지점 명칭)이며 두번째(second)가 거리 값
        int node_idx = pq.top().first;
        pq.pop();
  
        // node_idx 의 모든 인접 노드를 구한다
        for ( auto x : adj_nodes[node_idx] )
        {
            // node_idx 노드의 현재 인접한 노드의 정점의 이름과 거리값을 구한다
            int idx = x.first; // 노드
            int len = x.second; // 거리
  
            // idx 에서 node_idx 까지의 짧은 경로가 있으면
            if ( dist[idx] > dist[node_idx] + len )
            {
                // idx 거리를 업데이트 한다
                dist[idx] = dist[node_idx] + len;
                if ( idx != end )
                {
                    pq.push(make_pair(idx, dist[idx]));
                }
                
                parents[idx] = node_idx;
                //printf("idx: %d\n", idx);
            }
        }
    }
  
    printf("Result: %d to %d, cost: %d\n", start, end, dist[end]);
    printPath(end, parents);
    printf("\n");

    return dist[end];
}

int main(void)
{
    size_t nodes_num;
    int start, end, sum = 0;

    nodes_num = 9;
    vector<intPair > *adj_nodes = new vector<intPair >[nodes_num];

    // making above shown graph
    add_node(adj_nodes, 0, 1, 4);
    add_node(adj_nodes, 0, 7, 8);
    add_node(adj_nodes, 1, 2, 8);
    add_node(adj_nodes, 1, 7, 11);
    add_node(adj_nodes, 2, 3, 7);
    add_node(adj_nodes, 2, 8, 2);
    add_node(adj_nodes, 2, 5, 4);
    add_node(adj_nodes, 3, 4, 9);
    add_node(adj_nodes, 3, 5, 14);
    add_node(adj_nodes, 4, 5, 10);
    add_node(adj_nodes, 5, 6, 2);
    add_node(adj_nodes, 6, 7, 1);
    add_node(adj_nodes, 6, 8, 6);
    add_node(adj_nodes, 7, 8, 7);
    
    start = 4;
    end = 8;
    sum += get_shortest_distance(adj_nodes, nodes_num, start, 0);
    sum += get_shortest_distance(adj_nodes, nodes_num, 0, end);

    printf("The distance between %d and %d via 0 is: %d\n", start, end, sum);
    
    delete[] adj_nodes;
  
    return 0;
}