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

int minimumDist(double dist[], bool Tset[]) 
{
	int min=INT_MAX,index;
              
	for(int i=0;i<7;i++) 
	{
		if(Tset[i]==false && dist[i]<=min)      
		{
			min=dist[i];
			index=i;
		}
	}
	return index;
}

void Dijkstra(double graph[7][7],int src)
{
	double dist[7];                           
	bool Tset[7];
    int path[7][30];
    vector<int> paths[7];
	
 
	for(int i = 0; i<7; i++)
	{
		dist[i] = INT_MAX;
		Tset[i] = false;	
	}
	
	dist[src] = 0;           
	
	for(int j = 0; j<7; j++)                           
	{
		int m=minimumDist(dist,Tset);
		Tset[m]=true;
		for(int i = 0; i<7; i++)                  
		{
			
            if(!Tset[i] && graph[m][i] && dist[m]!=INT_MAX && dist[m]+graph[m][i]<dist[i] && graph[m][i] >= 0)
            {	
                dist[i]=dist[m]+graph[m][i];
                path[j][i] = m;
                for (int k = 0; k < paths[m].size(); k++)
                    paths[i].push_back(paths[m][k]);
                paths[i].push_back(m);
            }
		}
	}
	cout<<"Vertex\t\tDistance from source"<<endl;
	for(int i = 0; i<7; i++)                      
	{ //Printing
		char str=65+i; // Ascii values for pritning A,B,C..
		cout<<str<<"\t\t"<<dist[i]<<endl;
	}
    for(int i = 0; i<7; i++)                      
	{ //Printing
        paths[i].push_back(i);
        char str=65+i;
        cout<<"Path for "<<str<<" :";
		for (int j = 0; j < paths[i].size(); j++)
        {    
            char str=65+paths[i][j];
            cout<<str<<" ";
        }
        cout<<endl;
	}
    
}

int main()
{
	double graph[7][7]={
		{0.00,-1.00,1.12,-1.00,-1.00,-1.00,4.00,},
		{-1.00,0.00,3.04,1.41,5.39,-1.00,-1.00,},
		{1.12,3.04,0.00,2.50,-1.00,-1.00,4.61,},
		{-1.00,1.41,2.50,0.00,5.00,-1.00,-1.00,},
		{-1.00,5.39,-1.00,5.00,0.00,3.16,-1.00,},
		{-1.00,-1.00,-1.00,-1.00,3.16,0.00,3.61,},
		{4.00,-1.00,4.61,-1.00,-1.00,3.61,0.00,}};
	Dijkstra(graph,0);
	return 0;	                        
}




















#include <iostream>
#include <vector>
#include <boost/geometry.hpp>
#include <boost/geometry/geometries/geometries.hpp>
#include <boost/geometry/geometries/segment.hpp>
#include <boost/geometry/geometries/linestring.hpp> 
#include <boost/geometry/geometries/point.hpp>
#include <boost/geometry/geometries/polygon.hpp>
#include <iomanip>
#include <boost/geometry/algorithms/intersection.hpp>

namespace bg = boost::geometry;

int main()
{
    std::cout << std::fixed;
    std::cout << std::setprecision(2);
    
    typedef bg::model::point<double, 2, bg::cs::cartesian> point_t;
    typedef bg::model::segment<point_t> segment_t;
    typedef bg::model::linestring<point_t> linestring_t;
    typedef bg::model::polygon<point_t> polygon_t;

    polygon_t poly1{
        {{-0.5, 1.0}, {1.0, 3.0}, {5.0, 6.0}, {6.0, 3.0}, {4.0, 0.0}, {-0.5, 1.0}},
        {}
    };
    linestring_t ls1{{0.0, 0.0}, {0.0, 4.0}};
    
    polygon_t poly11{
        {{-0.5, 1.0}, {0, 4.0}, {2.0, 2.0}, {3.0, 5.0}, {6.0, 3.0}, {2.0, 0.0}, {-0.5, 1.0}},
        {}
    };
    linestring_t ls11{{0.0, 0.9}, {3, -1}};
    
    bg::correct(ls11);
    std::vector<point_t> all_points;
    std::vector<point_t> output;
    bg::intersection(ls11, poly11, output);
    
    if (output.size() > 0)
    {
        std::cout<<"Number of Intersection points:"<<output.size()<<std::endl;
        double x, y;
        for (int i = 0; i < output.size(); i++)
        {
            x = bg::get<0>(output[i]);
            y = bg::get<1>(output[i]);
            std::cout<<"x:"<<x<<" y:"<<y<<std::endl;
        }
        point_t p1;
        bg::set<0>(p1, 0);
        bg::set<1>(p1, 0);
        point_t p2;
        bg::set<0>(p2, 0);
        bg::set<1>(p2, 4);

        all_points.push_back(p1);
        all_points.push_back(p2);
        
        for (int v = 0; v < boost::geometry::exterior_ring(poly1).size() - 1; v++)
        {
            point_t p = boost::geometry::exterior_ring(poly1)[v];

            all_points.push_back(p);

        }
        
        float mat[all_points.size()][all_points.size()];
        
        for (int v1 = 0; v1 < all_points.size(); v1++)
        {
            point_t p1 = all_points[v1];
            double x1 = bg::get<0>(p1);
            double y1 = bg::get<1>(p1);
            for (int v2 = 0; v2 < all_points.size(); v2++)
            {
                point_t p2 = all_points[v2];
                double x2 = bg::get<0>(p2);
                double y2 = bg::get<1>(p2);
                linestring_t temp_ls1 {{x1, y1}, {x2, y2}};
                
                std::vector<point_t> tempoutput;
                boost::geometry::intersection(temp_ls1, poly1, tempoutput);
                
                if (tempoutput.size() == 0)
                {
                    mat[v1][v2] = bg::distance(p1, p2);
                }
                else if(tempoutput.size() == 1)
                {
                    bool check_touches = bg::touches(temp_ls1, poly1);
                    if (check_touches)
                    {
                        mat[v1][v2] = bg::distance(p1, p2);
                    }
                    else
                    {
                        mat[v1][v2] = -1;
                    }
                }
                else
                    mat[v1][v2] = -1;
                
            }
        }
        std::cout<<"MATRIX"<<std::endl;
        for (int j = 0; j < all_points.size(); j++)
        {
            std::cout<<"{";
            for (int i = 0; i < all_points.size(); i++)
                std::cout<<mat[j][i]<<",";
            std::cout<<"}"<<std::endl;
        }
    }
    else
    {
        std::cout<<"Doesn't Intersect"<<std::endl;
    }
    
    return 0;
}