class Solution {
public:
	void GetPath(vector<vector<int>>vec,int v0) {
		int size = vec.size();
		int S[MAX], k, minval;
		
		vector<int>dist(size);//dist存放单源最短路径
		vector<int>path(size);

		//初始化
		for (int i = 0; i < size; i++) {
			dist[i] = vec[v0][i];
			if (dist[i] != MAX)path[i] = v0;
			else path[i] = -1;
		}
		S[v0] = 1;
		dist[v0] = 0; 
		int num = 1;
		path[v0] = -1;
		while (num < size) {
			k = 0; minval = MAX;
			for(int i=0;i<size;i++)
				if ((dist[i] < minval) && (S[i] != 1)) {
					minval = dist[i];
					k = i;
				}
			S[k] = 1;
			for(int i=0;i<size;i++)
				if ( dist[k] + vec[k][i]<dist[i] ) {
					dist[i] = dist[k] + vec[k][i];
					path[i] = k;
				}
			num++;
		}
		cout<<"\n源点到各顶点的最短路径长和路径：";
		for (int i = 0; i != size; i++) {
			if (i == v0 )cout << "\n"<<dist[i]<< "\tpath:" << i << " <- " << v0;
			else if (dist[i] == MAX)cout<<"\n无路径" << "\tpath:" << i << " <- " << v0;
			else {
				cout << "\n" << dist[i] << "\tpath:" << i << " ";
				int pre = path[i];
				while (pre != -1) {
					cout << " <- " << pre << ' ';
					pre = path[pre];
				}
			}
		}
	}

};