b2007dlg.cpp

2007高教社杯全国大学生数学建模竞赛题目B题：乘公交

				m_Lines[curLine*2].m_pSations[pStations[0]] = station;
				
				for(int i = 1; i<nCount -1; i++)
				{
					memset(&station,0,sizeof(station));
					station.m_wSeq = i+1;
					station.m_wNext = pStations[i+1];
					station.m_wLast = pStations[i-1];

					m_Lines[curLine*2].m_pSations[pStations[i]] = station;
					
				}

				//Last
				station.m_wSeq = nCount;
				station.m_wNext = 0;
				station.m_wLast = pStations[i-1];
				
				m_Lines[curLine*2].m_pSations[pStations[i]] = station;

				for(i = 0; i<nCount; i++)
				{
					m_Lines[curLine*2+1].m_pSations[pStations[nCount -1 - i]].m_wSeq = i;
					m_Lines[curLine*2+1].m_pSations[pStations[nCount -1 - i]].m_wLast = m_Lines[curLine*2].m_pSations[pStations[i]].m_wNext;
					m_Lines[curLine*2+1].m_pSations[pStations[nCount -1 - i]].m_wNext = m_Lines[curLine*2].m_pSations[pStations[i]].m_wLast;
				}
			}

			delete []pStations;
		}

	} while(TRUE);

	f.Close();

	EndWaitCursor();
	GetDlgItem(IDC_INIT)->EnableWindow(FALSE);
	GetDlgItem(IDC_QUERY)->EnableWindow(TRUE);

}

void CB2007Dlg::OnQuery() 
{
	// TODO: Add your control notification handler code here
	UpdateData();

	if(m_nBegin == m_nEnd)
	{
		MessageBox("开始点等于结束点");
		return;
	}

	if(m_nBegin >= MAX_STAION)
	{
		MessageBox("开始点太大");
	}

	if(m_nEnd >= MAX_STAION)
	{
		MessageBox("结束点太大");
	}

	CString strResult;

	Element * tbl = new Element[MAX_STAION];
	
	tbl[m_nBegin].m_Added = TRUE;
// 	tbl[m_nBegin].m_costs.m_Changes = 0;
// 	tbl[m_nBegin].m_costs.m_Money = 0;
// 	tbl[m_nBegin].m_costs.m_Time = 0;
// 	tbl[m_nBegin].m_costs.m_walk = 0;

	//(1)初始化
	WORDLIST lstLines;
	GetLines(m_nBegin,lstLines);

	//每条线路
	POSITION pos = lstLines.GetHeadPosition();
	while(pos != NULL)
	{
		//
		WORD wLine = lstLines.GetNext(pos);
		
		//这条线路
		CLineInfo& Line = m_Lines[wLine];
		BOOL bCircular = Line.IsCircular();

		WORD wCurStation = m_nBegin;
		WORD nStationCount = 1;//相邻一站
		do 
		{
			//下个站点
			WORD wNextStation = Line.m_pSations[wCurStation].m_wNext;
			//合法站点?

			BOOL bValid = FALSE;
			if(wNextStation != 0)//不是终点的下一站
			{
				if(bCircular && wNextStation != m_nBegin)//不是环线的开始站
				{
					bValid = TRUE;
				}
			}

			if(!bValid) break;

			//计算代价
			Cost cost;
			cost.m_walk = 0;
			//费用类别
			if(Line.m_FeeType == fe_Fix)
			{
				cost.m_Money = Line.m_Fee.Yuan;
			}
			else
			{
				ASSERT(Line.m_FeeType == fe_Float);
				cost.m_Money = (nStationCount + Line.m_Fee.Section-1)/Line.m_Fee.Section;
			}
			//多少站？
			cost.m_Time = nStationCount * BUS_RUN_TIME;//TODO 地铁
			cost.m_Changes = 0;

			BOOL bUpdate = FALSE;

			if(cost.m_Time < tbl[wNextStation].m_costs.m_Time)//TODO 优化时间
			{
				bUpdate = TRUE;
			}

			if(bUpdate)//更新?
			{
				tbl[wNextStation].m_costs = cost;
				RouteNode node;
				node.m_wLine = wLine;
				node.m_wStation = wNextStation;
				node.m_nCount = nStationCount;
				
				//第一次，全部更新 以后只更新本次
				if(!tbl[wNextStation].m_Routes.IsEmpty())
				{
					tbl[wNextStation].m_Routes.RemoveAll();
					tbl[wNextStation].m_Routes.AddTail(node);
				}
			}

			wCurStation = wNextStation;

		} while(TRUE);
		
	}
	//End (1)

	do 
	{
		//(2)寻找一个不在N中的节点,花费最小
		//如果终点是花费最小的点，则结束

		UINT nMinPos = 0;//无效点
		for(int i = 2; i<MAX_STAION; i++)
		{
			Element &ele = tbl[i];
			if(ele.m_Added) continue;

			if(nMinPos == 0)
			{
				nMinPos = i;
				continue;
			}

			if(ele.m_costs.m_Time < tbl[nMinPos].m_costs.m_Time)//TODO
			{
				nMinPos = i;
			}
		}

		if(nMinPos == 0) break;//找完了

		if(nMinPos == m_nEnd)//找到了
		{
			MessageBox("找到了");
			break;
		}

		tbl[nMinPos].m_Added = TRUE;//加入集合

		//所有换乘线路
		GetLines(nMinPos,lstLines);

		//每条线路
		POSITION pos = lstLines.GetHeadPosition();
		while(pos != NULL)
		{
			//
			WORD wLine = lstLines.GetNext(pos);
			
			//这条线路
			CLineInfo& Line = m_Lines[wLine];
			BOOL bCircular = Line.IsCircular();

			WORD wCurStation = m_nBegin;
			WORD nStationCount = 1;//相邻一站

			//所有站点

			do 
			{
				//下个站点
				WORD wNextStation = Line.m_pSations[wCurStation].m_wNext;
				//合法站点?

				BOOL bValid = FALSE;
				if(wNextStation != 0)//不是终点的下一站
				{
					if(bCircular && wNextStation != m_nBegin)//不是环线的开始站
					{
						bValid = TRUE;
					}
				}

				if(!bValid) break;

				//计算代价
				Cost cost;
				cost.m_walk = WALK_BUS_BUS;//换乘
				//费用类别
				if(Line.m_FeeType == fe_Fix)
				{
					cost.m_Money = Line.m_Fee.Yuan;
				}
				else
				{
					ASSERT(Line.m_FeeType == fe_Float);
					cost.m_Money = (nStationCount + Line.m_Fee.Section-1)/Line.m_Fee.Section;
				}
				//多少站？
				cost.m_Time = nStationCount * BUS_RUN_TIME;//TODO 地铁
				cost.m_Changes = 1;

				BOOL bUpdate = FALSE;

				if(cost.m_Time < tbl[wNextStation].m_costs.m_Time)//TODO 优化时间
				{
					bUpdate = TRUE;
				}

				if(bUpdate)//更新?
				{
					tbl[wNextStation].m_costs = cost;
					RouteNode node;
					node.m_wLine = wLine;
					node.m_wStation = wNextStation;
					node.m_nCount = nStationCount;
					
					//第一次，全部更新 以后只更新本次
					if(!tbl[wNextStation].m_Routes.IsEmpty())
					{
						tbl[wNextStation].m_Routes.RemoveAll();
						tbl[wNextStation].m_Routes.AddTail(node);
					}
				}

				wCurStation = wNextStation;

			} while(TRUE);
			
		}

		//End (2)
	} while(TRUE);
	
	delete[]tbl;
}

CString CB2007Dlg::GetPath()
{
	CString strPath;
	
	TCHAR szFullPath[MAX_PATH];
	TCHAR szDir[_MAX_DIR];
	TCHAR szDrive[_MAX_DRIVE];
	
	//Get application's full path.
	::GetModuleFileName(NULL, szFullPath, MAX_PATH);
	
	//Break full path into separate components.
	_splitpath(szFullPath, szDrive, szDir, NULL, NULL);
	strPath = szDir;
	return strPath;
}

int CB2007Dlg::ParseLine(CString strNotToUse,WORD *pNum,WORD wLine)
{
	CString strLine = strNotToUse;

	ASSERT(pNum != NULL);
	int nReturn = 0;
	int nPos = 0;
	while((nPos = strLine.Find('-')) != -1)
	{
		CString str = strLine.Left(nPos);
		strLine = strLine.Mid(nPos+1);
		pNum[nReturn]=atoi(str.Mid(1));//S,D, etc
		nReturn ++;
	}
	
	//the Last one
	pNum[nReturn]=atoi(strLine.Mid(1));//S,D, etc
	nReturn ++;

	for(int i = 0; i< nReturn; i++)
	{
		for(int j = i+1; j< nReturn ; j++)
		{
			
			if(pNum[i] == pNum[j])
			{
				if((i == 0) && (j == nReturn-1))
				{
					continue;
				}
				else
				{
					TRACE("\n错误(%d)%d %d %d:"+strNotToUse,wLine,i+1,j+1,nReturn);
				}
				
			}
		}
	}
	return nReturn;
}

void CB2007Dlg::GetLines(WORD wStation, WORDLIST& lstReturn)
{
	lstReturn.RemoveAll();
	for(int i = 1; i< 2*MAX_LINE; i++)
	{
		if(m_Lines[i].m_pSations[wStation].m_wSeq != 0)
		{
			lstReturn.AddTail(WORD(i));
		}
	}

}