这周要交的算法作业：

1、编程作业：6.6练习题第7、9、10题。每道题编程调试成功后将程序和运行结果分别截图，保存到同一个word文档中，用学号+姓名命名后提交到第六章作业文件夹。作业提交截止时间：3月26日23:00。

9.有一个含n个顶点(顶点编号为0～n―1)的带权图,用邻接矩阵数组A表示,采用分枝限界法求从起点s到目标点t的最短路径长度﹐以及具有最短路径长度的路径条数。

#include <iostream>
#include <queue>

constexpr auto MAX = 20;
//#define MAX 20  如果上面那一行报错的话就删掉换成这一行  Visual Studio不会报错，其它工具不确定

constexpr auto INF = 0x3f3f3f3f;  //设置一个常量用来代表“无穷大”
//#define INF 0x3f3f3f3f   如果上面那一行报错的话就删掉换成这一行

using namespace std;


int A[MAX][MAX] = {
{0, 1, 4, INF, INF},
{INF, 0, INF, 1, 5},
{INF, INF, 0, INF, 1},
{INF, INF, 2,0,3},
{INF,INF,INF,INF,INF}
};
//临阶矩阵A


int n = 10;
int bestlen = INF;
int bestcount = 0; //统计
struct NodeType
{
	int vno;
	int length;
	bool operator<(const NodeType& s) const
	{
		return length > s.length;
	}
};
//使用结构体来存储数据


void shortpath(int s, int t)
{
	priority_queue<NodeType> qu;
	NodeType e{}, e1{};
	e.vno = s;
	e.length = 0;
	qu.push(e); //将e压入队列的末端
	while (!qu.empty())
	{
		e = qu.top(); qu.pop();
		if (e.vno == t) //e是一个叶子结点
		{
			if (e.length < bestlen)
			{
				bestcount = 1;
				bestlen = e.length;
			}
			else if (e.length == bestlen)
				bestcount++;
		}
		else
		{
			for (int j = 0; j < n; j++)
				if (A[e.vno][j] != INF && A[e.vno][j] != 0)
				{
					if (e.length + A[e.vno][j] < bestlen)
					{
						e1.vno = j;
						e1.length = e.length + A[e.vno][j];
						qu.push(e1);
					}
				}
		}
	}
}
int main()
{
	while (true)
	{
		int s, t;
		cout << "输入起点s:";
		cin >> s;
		cout << "输入终点t:";
		cin >> t;
		shortpath(s, t);
		if (bestcount == 0) {
			cout << "没有路径" << endl;
		}
		else {
			cout << "最短路径长度为" << bestlen << endl << "条数为" << bestcount << endl;
		}
	}//while是我方便测试才放的，作业可以去掉
	return 0;
}