#include
#include
#define?INF?9999
#define?VIS?1
#define?UNVIS?0
using?namespace?std;
class?graph{
public:
	int?**?matrix;
	string?*?vertex;
	int?vertex_num;
	int?current_size;
	graph（int?vertex_num=5）
	{
		

		if（vertex_num<=0）
		{
			cout<<“vertex_num?erro“<			exit（1）;
		}
		this->current_size=0;
		this->vertex_num=vertex_num;
		vertex?=?new?string[vertex_num];
		matrix?=?new?int*[vertex_num];
		for?（int?i?=?0;?i?		{
			matrix[i]?=??new?int[vertex_num];
		}


		//matrix初始化
		for?（int?i?=?0;?i??vertex_num;?i++）
		{
			for?（int?j?=?0;?j??vertex_num;?j++）
			{
				if（i==j）
					matrix[i][j]=0;
				else
					matrix[i][j]=INF;
			}
		}

	}
	void?insert（string?vertex_value）
	{
		if（current_size==vertex_num）
		{
			cout<<“oversize“<			return;
		}

		vertex[current_size++]?=?vertex_value;
		
	}
	void?link（int?aint?bint?weight）
	{
		if（weight<=0）
		{
			cout<<“weight?erro“<			return;
		}
		//vertex[0]??vertex[current_size-1]
		if（a		{
			matrix[a][b]=weight;?
		}

		else
		{

			cout<<“頂點下標越界:“<		}

	}

	void?show（）
	{
		for?（int?i?=?0;?i?		{
			cout<		}
		cout<
		for?（int?i?=?0;?i?		{
			for?（int?j?=?0;?j?			{
				cout<			}
			cout<		}
	}

	void?dijstra（int?sint?*?Dint?*?path）
	{

		bool?*?mark?=?new?bool[current_size];

		for?（int?i?=?0;?i?		{
			mark[i]=UNVIS;
			path[i]=-1;
			D[i]=INF;
		}
		D[s]=0;
		
		path[s]=s;

		for?（int?i?=?0;?i?		{
			int?min_sum=INF;
			int?min_ver=0;

		
			//在到所有頂點的現有路徑中找一條最小的
			for?（int?j?=?0;?j?			{
				if（D[j]				{
					min_sum?=?D[j];
					min_ver?=?j;
				}
			}

			mark[min_ver]=VIS;//添加頂點
			//更新該頂點的附近邊
			for?（int?i?=?0;?i?			{
				if（??mark[i]==UNVIS?&&????（matrix[min