1003Emergency

↪

February 15, 2020 AlgorithmDijkstraC++

Question

n个城市共有m条路,每个城市都设有救援小组,所有的边的边权(救援小组数目)已知,给定起点和终点,求从起点到终点的最短路径的条数,以及最短路径上救援小组最多的数目之和. 每个输入包含一个测试用例，第一行包含四个正整数N（N<=500）--城市数量（城市从0-N-1编号），M--道路数量，c1，c2--起点和终点。下一行包括N个整数，其中第i个整数是第i个城市的救援队数量。然后是M条线，每条线描述了一条具有三个正整数c1，c2和L的道路，分别对应两个城市以及城市之间的路线长度。

Sample Input

5 6 0 6
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

这道题呢解题用到了Dijkstra算法，先推荐一个讲的比较好的Dijkstra算法的博文

 这个算法的特点是使用了广度优先搜索解决了赋权有向图或者无向图的单源最短路径问题，算法最终可以得到一个最短路径树。

 大体思路可以理解成:首先声明一个数组来保存起点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合T，初始时，将起点的本点的路径距离设为0， 对于起点能够到达的边的距离设为两点距离，其他点设为无穷大。初始时，T中只有起点，然后从已经保存的最短路径中找到最小值，那么该值就是该点到原点的最短路径，将该点加入到T中， 然后我们观察新加入的点是否可以到达其他顶点并且通过该点到其他点的距离加上原点到该点的距离是不是比原点到相应的点的距离小，小的话，就把新的距离替换之前的最短距离，然后再重复上述动作， 直到T中包含了所有顶点。

 再看这道题，跟典型的dijkstra解决的问题很相似，只不过我们需要在跟最短路径相同的时候也要将新路径统计上，然后就是要选择出路径中权值和最大的。

 判定的核心： 当新开始判定一个点的时候，如果当前节点的最短路径加上当前节点到判定节点的距离<判定节点之前存储的最短路路径，那么判定节点最短路径 = 当前节点的最短路径加上当前节点到判定节点的距离，最短路径的条数 = 当前节点的最短路径的条数，判定节点的最大小组营救数 = 当前最大营救小组数+判定节点的小组营救数。

 如果当前节点的最短路径加上当前节点到判定节点的距离==判定节点之前存储的最短路路径，那么最短路径的条数 += 当前节点的最短路径的条数，最大小组营救数要比较之前存储的和现在新的路线的最大营救小组数哪个多。

 另外，要注意这是一个无向图（监测点2，5）并且注意判定起点终点相同时的情况（监测点1）。

AC代码:

//date:2020.02.10
//author:ViViWilliam
//issue3
#include<iostream> 
using namespace std;
int main(){
	//城市数,道路数,所在地,目的地 
	int N,M,c1,c2; 
	cin>>N>>M>>c1>>c2;
	int team[N]={0};
	int road[N][N];
	int length[N]={0};
	int teamsum[N]={0};
	int min[N]={0},sum;
	sum=0;
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			road[i][j]=10000;
		}
	}
	for(int i=0;i<N;i++){
		cin>>team[i];
	}
	
	for(int i=0;i<M;i++){
		int x,y; 
		cin>>x;
		cin>>y;
		cin>>road[x][y];
		road[y][x] = road[x][y];
	}
	
	for(int i=0;i<N;i++){
		length[i]=road[c1][i];
		if(road[c1][i]!=10000){
		teamsum[i] = team[i]+team[c1];
			min[i]=1;
		}
				
	}
	length[c1]=0;
	min[c1]=1;
	teamsum[c1] = team[c1];
	
	int last,lastnum;
	int i;
	int h[N]={0};
	h[c1]=1;
	int a=0;

	
	while(1){
		
		int minid=10000,minro=10000;
		//找到一个起始点 
		for(int d=0;d<N;d++){
			if (h[d]==0){
				minid=d;
				minro=length[d];
				break;
			}
		}
		//所有点都遍历完 
		if(minid==10000)
		break;
		//找出最小值,作为起点 
		for(int m=0;m<N;m++){
			if(h[m]==0&&length[m]<minro){
				minid = m;
				minro = length[m];
			}
		}
		h[minid]=1;
		i = minid;
			if(i == c1){
				continue;
			}
			//依次排查 
			for(int j=0;j<N;j++){
				if(h[j] == 0 && road[i][j] != 10000){
				
				if(j==c1)
					continue;
				//如果当前位置的长度加上此位置到某点的位置小于等于 
				if((length[i]+road[i][j])<=length[j]){

					//如果小于,总的 					
						if((length[i]+road[i][j])<length[j]){
							teamsum[j] = teamsum[i]+team[j];
							length[j] = length[i]+road[i][j];
							min[j] = min[i];
						}
						else if(length[i]+road[i][j]==length[j]){
							min[j]+=min[i];
							if(teamsum[j]<(teamsum[i]+team[j])){
							teamsum[j]=teamsum[i]+team[j];
						}
						
					
				}	
		    }
		    }
			}


	} 
	cout<<min[c2]<<" "<<teamsum[c2];
return 0; 
}