#include??
#include
#include
using?namespace?std;
#define?MAXWEIGHT?100
#undef?INFINITY
#define?INFINITY?1000
class?Graph
{
private:
	//頂點數(shù)??
	int?numV;
	//邊數(shù)??
	int?numE;
	//鄰接矩陣??
	int?**matrix;
public:
	Graph（int?numV）;
	//建圖??
	void?createGraph（int?numE）;
	//析構(gòu)方法??
	~Graph（）;
	//Floyd算法
	void?Floyd（）;
	//打印鄰接矩陣??
	void?printAdjacentMatrix（）;
	//檢查輸入??
	bool?check（int?int?int）;
};
//構(gòu)造函數(shù)，指定頂點數(shù)目
Graph::Graph（int?numV）
{
	//對輸入的頂點數(shù)進行檢測
	while?（numV?<=?0）
	{
		cout?<		cin?>>?numV;
	}
	this->numV?=?numV;
	//構(gòu)建鄰接矩陣，并初始化
	matrix?=?new?int*[numV];
	int?i?j;
	for?（i?=?0;?i?		matrix[i]?=?new?int[numV];
	for?（i?=?0;?i?	for?（j?=?0;?j?	{
		if?（i?==?j）
			matrix[i][i]?=?0;
		else
			matrix[i][j]?=?INFINITY;
	}
}
void?Graph::createGraph（int?numE）
{
	/*
	對輸入的邊數(shù)做檢測
	一個numV個頂點的有向圖，最多有numV*（numV?-?1）條邊
	*/
	while?（numE??numV*（numV?-?1））
	{
		cout?<		cin?>>?numE;
	}
	this->numE?=?numE;
	int?tail?head?weight?i;
	i?=?0;
	cout?<	while?（i?	{
		cin?>>?tail?>>?head?>>?weight;
		while?（!check（tail?head?weight））
		{
			cout?<			cin?>>?tail?>>?head?>>?weight;
		}
		matrix[tail][head]?=?weight;
		i++;
	}
}
Graph::~Graph（）
{
	int?i;
	for?（i?=?0;?i?		delete[]?matrix[i];
	delete[]matrix;
}
/*
弗洛伊德算法
求各頂點對之間的最短距離
及其路徑
*/
void?Graph::Floyd（）
{
	//為了不修改鄰接矩陣，多用一個二維數(shù)組
	int?**Distance?=?new?int*[numV];
	int?i?j;
	for?（i?=?0;?i?		Distance[i]?=?new?int[numV];
	//初始化
	for?（i?=?0;?i?	for?（j?=?0;?j?		Distance[i][j]?=?matrix[i][j];

	//prev數(shù)組
	int?**prev?=?new?int*[numV];
	for?（i?=?0;?i?		prev[i]?=?new?int[numV];
	//初始化prev
	for?（i?=?0;?i?	for?（j?=?0;?j?	{
		if?（matrix[i][j]?==?INFINITY）
			prev[i][j]?=?-1;
		else
			prev[i][j]?=?i;
	}
	
	int?d?v;
	for?（v?=?0;?v?	for?（i?=?0;?i