MOOC 数据结构 1003 Emergency

As an emergency rescue team leader of a city, you are given a special map of your country. The map shows several scattered cities connected by some roads. Amount of rescue teams in each city and the length of each road between any pair of cities are marked on the map. When there is an emergency call to you from some other city, your job is to lead your men to the place as quickly as possible, and at the mean time, call up as many hands on the way as possible.

Input Specification:

Each input file contains one test case. For each test case, the first line contains 4 positive integers: N (≤500) - the number of cities (and the cities are numbered from 0 to N−1), M - the number of roads, C1​ and C2​ - the cities that you are currently in and that you must save, respectively. The next line contains N integers, where the i-th integer is the number of rescue teams in the i-th city. Then M lines follow, each describes a road with three integers c1​, c2​ and L, which are the pair of cities connected by a road and the length of that road, respectively. It is guaranteed that there exists at least one path from C1​ to C2​.

Output Specification:

For each test case, print in one line two numbers: the number of different shortest paths between C1​ and C2​, and the maximum amount of rescue teams you can possibly gather. All the numbers in a line must be separated by exactly one space, and there is no extra space allowed at the end of a line.

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

 整理总结：这是一道考察有权图的单源最短路径问题，核心算法是Dijkstra算法；但是有点不同，Dijkstra算法只考虑收录一个顶点时路径会变短的情况，路径相等时的情况没考虑，那么如果存在多条最短路怎么办

        对于这道题：①输出有几条最短路 增加一个数组Num[V]，为源点S到顶点V的最短路条数；初始化为0；给定源点S，Num[S] = 1，S的每个邻接点V，Num[V] = Num[S];Dijkstra算法执行的时候  dist[V] + G[V][W] < dist[W]  W继承V的最短路条数 Num[W] = Num[V] ；dist[V] + G[V][W] == dist[W] 时，Num[W] += Num[V]；

                             ②输出最短路径情况下沿途能带上的最大救援团队，增加一个数组team[]，为源点S以最短路到达顶点V时的救援队数量；初始化每个顶点V  team[V] = 每个顶点本来有的救援队数量(即点权)；给定源点S，对于S的每个邻接点V，team[V] += team[S]；Dijkstra算法执行的时候  dist[V] + G[V][W] < dist[W]  W的最大救援队数量 team[W] += team[V] ；dist[V] + G[V][W] == dist[W] 时，再根据team[]的大小来决定是否更新最短路

         所以不难看出这其实是另外一套问题：有权图多条最短路径问题

一般有以下4种情况：

1.增加另一个边权(比如:主权重考虑距离，当距离相等时考虑副权重花费cost)

2.增加点权：每个顶点有一个 权重，当有多条最短路时，考虑经过的点权

3.直接问有多少条最短路

4.终极问题：请输出每条最短路的具体路径

前3个问题 都是只增加相应的数组就可以解决；比如对应第一种情况增加边权的问题MOOC 数据结构 07-图6 旅游规划_鸿雁丨红豆灬的博客-CSDN博客

以及本题中的增加点权和直接问最短路径条数；

终极问题就必须保存每条最短路的具体路径，就不是增加一个数组就行的了，这也是其他问题的通用解法：得出了具体的不同最短路，根据实际需求分析每条最短路的优劣势，从而得出想要的答案；

我们先来看下这道题的代码，然后再来讨论终极问题的解法：

#include 
#include 
#include 
#define INFINITY 250000
#define ERROR -1

typedef int Vertex;     //顶点
typedef int WeightType; //边权
typedef int DataType;   //顶点数据(点权)
//边
typedef struct _Edge{
	Vertex V1,V2;
	WeightType Weight;
}Edge;
//邻接点
typedef struct _Adj Adj;
struct _Adj{
	Vertex AdjV;
	WeightType Weight;
	Adj* Next;
};
//邻接表存储的图
typedef struct _LGraph{
	int Nv; //顶点数
	int Ne; //边数
	DataType* Data; // 存放顶点数据的数组
	Adj** G;  //邻接表 G为链表数组，数组的每个元素是一个链表的头指针
}LGraph;

LGraph* BuildGraph( int N,int M );

LGraph* CreateGraph( int N,int M );

void InsertEdge( LGraph* Graph,Edge E );

void EmergencyRescue( LGraph* Graph,Vertex Start,Vertex Destination );

void Dijkstra( LGraph* Graph,Vertex S,WeightType dist[],Vertex path[],bool collected[],int MaxRescueTeams[],int Num[] );

Vertex FindMinDist( LGraph* Graph,WeightType dist[],bool collected[] );

int main()
{
	int N,M;
	Vertex Start,Destination;
	
	scanf("%d %d %d %d",&N,&M,&Start,&Destination);
	
	LGraph* Graph = BuildGraph( N,M );
	
	EmergencyRescue( Graph,Start,Destination );
	
	return 0;
}

LGraph* BuildGraph( int N,int M )
{
	LGraph* Graph = CreateGraph( N,M );
	
	Edge E;
	int i;
	for(i=0;iNe;i++){
		
		scanf("%d %d %d",&E.V1,&E.V2,&E.Weight);
		
		InsertEdge( Graph,E );
	}
	
	return Graph;
}

LGraph* CreateGraph( int N,int M )
{
	LGraph* Graph = (LGraph*)malloc(sizeof(LGraph));
	
	Graph->Nv = N;
	Graph->Ne = M;
	
	Graph->Data = malloc(Graph->Nv*sizeof(DataType));
	
	Graph->G = malloc(Graph->Nv*sizeof(Adj*));
	
	Vertex V;
	for(V=0;VNv;V++){
		
		scanf("%d",&(Graph->Data[V]));
		Graph->G[V] = NULL;
	}
	
	return Graph;
}

void InsertEdge( LGraph* Graph,Edge E )
{
	Adj* NewNode;
	
	NewNode = (Adj*)malloc(sizeof(Adj*));
	NewNode->AdjV = E.V1;
	NewNode->Weight = E.Weight;
	NewNode->Next = Graph->G[E.V2];
	Graph->G[E.V2] = NewNode;
	
	NewNode = (Adj*)malloc(sizeof(Adj*));
	NewNode->AdjV = E.V2;
	NewNode->Weight = E.Weight;
	NewNode->Next = Graph->G[E.V1];
	Graph->G[E.V1] = NewNode;
}

void EmergencyRescue( LGraph* Graph,Vertex Start,Vertex Destination )
{
	/* dijkstra算法过程中需要用到的数组 */
	WeightType dist[Graph->Nv];  //最短路数组
	Vertex path[Graph->Nv];      //具体路径数组,该题中不需要
	bool collected[Graph->Nv];   //已确定了最短路的顶点数组
	int MaxRescueTeams[Graph->Nv],Num[Graph->Nv]; //救援团队数组
	
	/* 各个数组的初始化 */
	Vertex V;
	for(V=0;VNv;V++){
		
		dist[V] = INFINITY;
		path[V] = -1;
		collected[V] = false;
		MaxRescueTeams[V] = Graph->Data[V];
		Num[V] = 0;
	}
	
	Dijkstra( Graph,Start,dist,path,collected,MaxRescueTeams,Num );
	
	printf("%d %d\n",Num[Destination],MaxRescueTeams[Destination]);
}

void Dijkstra( LGraph* Graph,Vertex S,WeightType dist[],Vertex path[],bool collected[],int MaxRescueTeams[],int Num[]  )
{
	/* 确定源点后的数组更新 */
	dist[S] = 0;
	collected[S] = true;
	Num[S] = 1;

	Adj* p;
	for(p=Graph->G[S];p;p=p->Next){
		
		dist[p->AdjV] = p->Weight;
		path[p->AdjV] = S;
		MaxRescueTeams[p->AdjV] = MaxRescueTeams[S] + Graph->Data[p->AdjV];
		Num[p->AdjV] = Num[S];
	}
	
	/*dijkstra算法的核心循环*/
	Vertex V;
	while(1){
		V = FindMinDist( Graph,dist,collected );
		
		if(V==ERROR) break;
		
		for(p=Graph->G[V];p;p=p->Next){
			
			if(collected[p->AdjV] == false){
				if(dist[V] + p->Weight < dist[p->AdjV]){ //有更短的路径时
					
					dist[p->AdjV] = dist[V] + p->Weight; //更新最短路
					path[p->AdjV] = V;
					MaxRescueTeams[p->AdjV] = MaxRescueTeams[V] + Graph->Data[p->AdjV];
					Num[p->AdjV] = Num[V];
				
				}else if(dist[V] + p->Weight == dist[p->AdjV]){ //有另一条最短路时
					
					Num[p->AdjV] += Num[V];
					
					if(MaxRescueTeams[V] + Graph->Data[p->AdjV] > MaxRescueTeams[p->AdjV]){
						
						path[p->AdjV] = V;
						MaxRescueTeams[p->AdjV] = MaxRescueTeams[V] + Graph->Data[p->AdjV];
					}
				}
			}
		}
		
		collected[V] = true;
	}
}

Vertex FindMinDist( LGraph* Graph,WeightType dist[],bool collected[] )
{
	Vertex V,MinID = ERROR;
	WeightType MinDist = INFINITY;
	
	for(V=0;VNv;V++){
		
		if(collected[V]==false && dist[V] < MinDist){
			
			MinDist = dist[V];
			MinID = V;
		}
	}
	
	return MinID;
}

最后，要输出每条最短路径时，我想了好久，特别是数据的存储和递归函数的设计，分享如下:

数据结构 Dijkstra算法 改良版 多条最短路径问题通用解决方案——C语言实现_鸿雁丨红豆灬的博客-CSDN博客