全部资源
全部资源
C/C++
C#
PHP
Java
Python
VB
ASP
Html/CSS
Matlab
JavaScript
数据库
模板
其他

中兴捧月算法大赛Dijkstra派解决方案

收藏(0)
  • 大小: 65KB
    文件类型: .rar
    金币: 1
    下载: 0 次
    发布日期: 2021-06-06
  • 语言: 其他
  • 标签: 中兴捧月  Dijkstra  
高速下载

资源简介

文件是本人参加2017年的中兴捧月算法大赛（Dijstra派）的代码和可执行文件，得分86，获得中南赛区区域优胜奖

资源截图

小图 大图

代码片段和文件信息 

#include
#include
#include
#include
#include
#include
#include
#include 
#include
using namespace std;




//起点，终点，边的总数量，必须经过的边数量，必须经过的点数量，必须经过的边的权重和
int srcNode dstNode edgeNum specialEdgeNum specialEdgeValue = 0;
int requestNum = 9;  //路径的节点数限制
map>edgeTable; //存储每个节点直接连接的节点
map int>valueTable; //存储每个边的花费
map bool>specialEdge;  //存储必须经过的边
mapspecialEdgeNode;
vector>midPath;//存储特殊点和特殊边所有可能的排序方式
vectorspecialNode;
vector>tmpedgeList;  //用向量的形式存储所有的边，并且一条边仅存储一次

//preNode用于记录每个节点的前驱节点
int dijstra（int src int dst map&preNode）
{

	mapcheck;
	check[src] = true;

	mapdisTable;

	vectortoDst = edgeTable[src];
	for （int i = 0; i < toDst.size（）; i++）
	{
		disTable[toDst[i]] = valueTable[pair（src toDst[i]）];
		preNode[toDst[i]] = src;
	}


	while （true）
	{
		int minValue = INT_MAX;
		int node = -1;

		map::iterator it = disTable.begin（）;
		for （; it != disTable.end（）; it++）
		{
			if （check.count（it->first） == 0 && disTable[it->first] < minValue）
			{
				minValue = disTable[it->first];
				node = it->first;
			}
		}


		if （node < 0）break; //表示无法找出下一个要添加的节点

		check[node] = true;


		if （node == dst）
			return minValue;

		vectorto = edgeTable[node];
		for （int i = 0; i < to.size（）; i++）
		{
			if （disTable.count（to[i]） == 0 ||
				disTable[to[i]]>disTable[node] + valueTable[pair（node to[i]）]）
			{
				disTable[to[i]] = disTable[node] + valueTable[pair（node to[i]）];
				preNode[to[i]] = node;
			}
		}
	}
	return -1;
}

//根据前驱节点计算路径
vectorCalcPath（int src int dst mappreNode）
{
	vectorresult;
	result.push_back（dst）;
	if （src == dst）return result;

	int p = dst;
	while （preNode[p] != src）
	{
		result.push_back（preNode[p]）;
		p = preNode[p];
	}
	result.push_back（src）;

	reverse（result.begin（） result.end（））;

	return result;
}
//根据经过的特殊点集顺序，计算出经过的完整点集
vector CalcFullPath（vectornodeList int&resultValue）
{
	vector result;

	mappreNode;
	for （int i = 1; i < nodeList.size（）; i++）
	{
	
		int src = nodeList[i - 1];
		int dst = nodeList[i];

		if （src == dst）
			continue;

		if （specialEdge.count（pair（src dst）） != 0）
		{
			if （result.empty（））
			{
				result.push_back（src）;
				result.push_back（dst）;
			}
			else
			{
				result.pop_back（）;
				result.push_back（src）;
				result.push_back（dst）;
			}


			resultValue += valueTable[pair（src dst）];
		}
		else
		{
			preNode.clear（）;
			int curResult = dijstra（src dst preNode）;

			if （curResult < 0）
			{
				//表示到dst不可达
				result.clear（）;
				break;
			}


			resultValue += curResult;
			vectorfullPath = CalcPath（src dst preNode）;

			if （r

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件        321  2017-05-11 20:19  code\可执行文件\data0.txt

     文件        321  2017-05-11 20:19  code\可执行文件\data1.txt

     文件        294  2017-05-11 20:19  code\可执行文件\data2.txt

     文件        321  2017-05-11 21:24  code\可执行文件\data3.txt

     文件        321  2017-05-11 20:19  code\可执行文件\data4.txt

     文件        321  2017-05-11 20:19  code\可执行文件\data5.txt

     文件        424  2017-05-11 20:20  code\可执行文件\data6.txt

     文件        621  2017-05-11 20:20  code\可执行文件\data7.txt

     文件     395264  2017-05-11 21:13  code\可执行文件\中兴捧月（不剪枝）.exe

     文件        157  2017-05-11 20:28  code\可执行文件\运行说明.txt

     文件        321  2017-05-11 20:19  code\数据集\data0.txt

     文件        321  2017-05-11 20:19  code\数据集\data1.txt

     文件        294  2017-05-11 20:19  code\数据集\data2.txt

     文件        321  2017-05-11 21:24  code\数据集\data3.txt

     文件        321  2017-05-11 20:19  code\数据集\data4.txt

     文件        321  2017-05-11 20:19  code\数据集\data5.txt

     文件        424  2017-05-11 20:20  code\数据集\data6.txt

     文件        621  2017-05-11 20:20  code\数据集\data7.txt

     文件        365  2017-05-11 20:18  code\数据集\输入的数据格式说明.txt

     文件         52  2017-05-11 15:14  code\源码\readme.txt

     文件      10723  2017-05-11 21:13  code\源码\源.cpp

     目录          0  2017-06-19 17:25  code\可执行文件

     目录          0  2017-06-19 17:25  code\数据集

     目录          0  2017-06-19 17:25  code\源码

     目录          0  2017-06-19 17:25  code

----------- ---------  ---------- -----  ----

               412449                    25


评论

共有 条评论