#include<iostream>

#include<stack>

#include<fstream>

using namespace std;

const int MaxNum=100000;

class Graph

{

private:

int *Adj; //保存邻接矩阵的一维数组 j和k之间权值 存储在

Adj[j*Num+k]中

int Num;//当前顶点数

public:

Graph(); //构造函数

~Graph();//析沟函数

void Dijkstra(int start);//单元最短路径算法

};

Graph::Graph() //构造函数

{

ifstream input("input.txt",ios::in);

if(input==NULL)cout<<"open error!\n";

if(input!=NULL)

{

input>>Num;

Adj=new int[Num*Num];

if(Adj==NULL)exit(0);

for(int i=0;i<Num;i++)

for(int j=0;j<Num;j++)

{

input>>Adj[i*Num+j];

if(Adj[i*Num+j]==-1)

Adj[i*Num+j]=MaxNum;

}

}

}

Graph::~Graph()//析构函数

{

delete []Adj;

}

void Graph::Dijkstra(int start)//单元最短路径算法

{

int*dist=new int[Num];//记录最短权值

int*prev=new int[Num]; //记录路径

int*s=new int[Num];//s为已经确定好的顶点域