输入格式和图见下方 n结点数，从1开始，k表示中间节点，求从1号点经过k号点到n号点的最短路径，并输出

alt

输入格式

5 3
1 2 10 5 30
2 3 20
3 4 60 5 10
4 5 20
5

#include<iostream>
#include<string>
#include<sstream>
#include<vector>
#include<fstream>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<stack>
using namespace std;
#define MAX 1<<29

//floyed算法
vector< vector<int> >g;//邻接矩阵,有向图
vector<vector<int>>path;//存放路径的二维数组
vector<int>mypath;
//将不包含终点的路径插入到mypath中
void getpath(int source,int destination) {
	if (source == destination)return;
	if (path[source][destination] == -1) {
		mypath.push_back(source);
	}
	else {
		int mid = path[source][destination];
		getpath(source, mid);
		getpath(mid, destination);
	}
}
int main() {
	int n; cin >> n;
	g.resize(n + 1); 
	for (int i = 1; i <= n; i++)g[i].resize(n + 1);//对邻接矩阵进行初始化
	path = g;
	for (int i = 1; i < g.size(); i++) {
		for (int j = 1; j < g.size(); j++) {
			if (i == j)g[i][j] = 0;
			else g[i][j] = MAX;
			path[i][j] = -1;
		}
	}
	cout << "g.size()=" << g.size() << endl;

	//输入获取矩阵
	int k; cin >> k;
	cin.get();
	string s="start";
	//getline(cin, s);
	//cout << "s=" << s << endl;
	while (s!="") {
		getline(cin, s);
		istringstream iss(s);
		int source; iss >> source;
		int d, len;
		while (iss >> d >> len) {
			g[source][d] = len;
		}
	}
	cout << "输入完成" << endl;
	//开始进行floyed算法
	vector< vector<int> >A; A = g;
	for (int v = 1; v <= n; v++) {//选中间点
		for(int i=1;i<=n;i++)//遍历临界矩阵
			for (int j = 1; j <= n; j++) {
				if (v == i || v == j || i == j)continue;

				if (A[i][j] > A[i][v] + A[v][j]) {
					A[i][j] = A[i][v] + A[v][j];
					path[i][j] = v;
				}
			}
	}

	cout << "运算完成" << endl;
	//运算完成，返回路径
	getpath(1, k);
	getpath(k, n);
	mypath.push_back(n);//再把终点推进去
	cout << "path=" << endl;
	for (int i = 0; i < mypath.size(); i++) {
		cout << mypath[i];
		if (i != mypath.size() - 1)cout << ",";
	}
	cout << endl;
	cout << "path[1][3]=" << path[1][3] << endl;


	return 0;
}