1003 Emergency 分支限界法（广度优先+剪枝）

目录

题目

输入样例

输出样例

提交结果截图

解题思路及源代码

题目

链接：1003 Emergency（PAT (Advanced Level) Practice） 

输入样例

5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1

输出样例

2 4

提交结果截图

解题思路及源代码

/********************************************
Sample Input:
5 6 0 2
1 2 1 5 3
0 1 1
0 2 2
0 3 1
1 2 1
2 4 1
3 4 1
Sample Output:
2 4

(Way->路线 Per->支援人数 Len->路线长度)
Way:    0->1->2
Per:    1  2  1  = 4
Len:     1  1    = 2
Way:    0->2
Per:    1  1 = 2
Len:     2   = 2
Way:    0->3->4->2
Per:    1  5  3  1 = 10 
Len:     1  1  1   = 3
......

优先考虑路线长度，路线短是第一要素，
如果路线长度相同，则支援人数越多越好

* 解题思路 *
1.将路径图存储，按照广度优先遍历，记录路径长度和
支援人数，若能够到达目标位置，则与先前得到的
最短路径进行比较，若是更短则更新路径、路径长度及相应
的支援人数，若是相等，则比较支援人数，支援人数多的
保存记录。
2.为方便存储城市路径关系，需建立临界矩阵
WayLength[500][500]
若是i城和j城有路径可以到达，
则WayLength[i][j] = 路径长度，否则
WayLength[i][j] = 0

********************************************/

#include <iostream>
#include <queue>
using namespace std;

int CityNum;//城市数量
int RoadsNum;//路径数量
int StartCityNum;//开始城市编号
int AimCityNum;//目标城市编号
int WayLength[500][500];//城市之间路径长度
int CityPerNum[500];//各城市的救援队数量
int ShortestPath[500];//最短的路径（仅供调试用）
int ShortestPathCityNum;//最短路径上的城市数量
int ShortestLen = -1;//最短路径的长度
int MaxPerNum;//所有最短路径中最多的救援队数量
int ShortestPathNum = 0;//最短路径的数量

//定义一个结构体存储当前路径的状态
struct state
{
	int cityNum;//经过的城市数（包括出发点）
    int CurrentCity;//当前的城市的编号
    int path[500];//城市路径
    int CurrentPathLen;//当前路径的长度
    int CurrentPerNum;当前路径所能召集的救援队数量
};

int main()
{
    queue<state>q;
    int startCityNum, endCityNum;//仅存储输入数据使用
    cin>>CityNum>>RoadsNum>>StartCityNum>>AimCityNum;
    for(int i = 0; i < CityNum; i++)
        cin>>CityPerNum[i];
    if(StartCityNum == AimCityNum)//特例：如果所需要救援的城市就是当前城市，直接输出即可
	{
		cout<<"1 "<<CityPerNum[StartCityNum];
			return 0;
	}
    for(int i = 0; i < RoadsNum; i++)
    {
        cin>>startCityNum>>endCityNum;
        cin>>WayLength[startCityNum][endCityNum];
		WayLength[endCityNum][startCityNum] = WayLength[startCityNum][endCityNum];
    }
    
    state q0;//定义一个队首，存储出发地状态
	q0.cityNum = 1;
	q0.CurrentCity = StartCityNum;
	q0.CurrentPathLen = 0;
	q0.CurrentPerNum = CityPerNum[StartCityNum];
	for(int i = 1; i < CityNum; i++)
		q0.path[i] = -1;
	q0.path[0] = StartCityNum;
    q.push(q0);

	state tmp;//定义一个临时的结构体，存储出队的数据

    while(!q.empty())
    {
        tmp = q.front();
        q.pop();
		int startCity = tmp.CurrentCity;
        for(int i = 0; i < CityNum; i++)
		{
            //查重：防止出现多次经过同一个城市的情况
			bool ifRepeat = false;
			for(int j = 0; j < tmp.cityNum; j++)
				if(tmp.path[j] == i)
					ifRepeat = true;
			if(ifRepeat)//如果重复则没必要执行后续操作
				continue;
            
			if(WayLength[startCity][i])//如果两城市间存在路径
            {
				state New = tmp;//拷贝tmp的数据（不能直接修改tmp）
				New.cityNum++;
				New.CurrentCity = i;
				New.CurrentPathLen += WayLength[startCity][i];
				New.CurrentPerNum  += CityPerNum[i];
				New.path[New.cityNum-1] = i; 
                if(i == AimCityNum)//如果走到了目标城市
                {
					if(New.CurrentPathLen == ShortestLen)//说明有新的最短路径且与之前的路径长度相等
						ShortestPathNum++;
                    else if(New.CurrentPathLen < ShortestLen || ShortestLen == -1)//路径更新或这是第一条路径
                        ShortestPathNum = 1;
					if(New.CurrentPathLen<ShortestLen || ShortestLen == -1 || 
						(New.CurrentPathLen == ShortestLen && New.CurrentPerNum >MaxPerNum))
					{
						ShortestLen = New.CurrentPathLen;
						MaxPerNum = New.CurrentPerNum;
						ShortestPathCityNum = New.cityNum;
						for(int i = 0; i < New.cityNum; i++)
							ShortestPath[i] = New.path[i];
					}
                }
				else if(New.CurrentPathLen < ShortestLen || ShortestLen == -1 )//剪枝函数，仅让可能取到最短路径的路径状态入队
					q.push(New);
            }
        }
    }
	cout<<ShortestPathNum<<" "<<MaxPerNum;
    return 0;
}