PAT甲级真题(迪杰斯特拉算法)——1003. Emergency (25)

1003 Emergency （25 分）

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​​ , c​2 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 C​1 and C​2, 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

题目大意：

有m个城市，n条路，路的长度不一，在第i个城市上有一定数量的搜救队。
现在从c1城出发，要抵达c2城，需要我们求的是c1到c2距离最短的路径条数，和一条最短路径上能召集到的救援队的最大数量。

题目分析：

求单源最短路径，可以用dijkstra算法。

• 城市中救援队数量为点权，路长度为边权；
• 用count[i]表示出发点到i点的最短路径数目，w[i]表示出发点到i点最短路径上救援队总数,dis[i]为出发点到i点的最短路径长度；

1. c1为出发点
2. count[c1]的初值显然为1，因为只有唯一一条路径；
3. w[c1]初值为c1城救援队数量；
4. dis[c1]为0。

在执行过程中，每次在未访问到的城市中取距离出发点距离最短的城市u，当作跳板。

核心算法：

    if(dis[u]+u到v的距离<dis[v]) {
    	更新dis[v],count[v],w[v]
    }
    else if(dis[u]+u到v的距离==dis[v]) {
    	更新count[v]
    	if(w[u]+v城市救援队数量>w[v])
    		更新w[v]
    }
	

具体代码：

    #include<iostream>
    #include<cstdio>
    #include<climits>
    
    const int MAXN=510;
    const int inf=INT_MAX;
    using namespace std;
    
    int n,e[MAXN][MAXN],weight[MAXN],dis[MAXN],vis[MAXN]= {false};
    int count[MAXN];//count[i]表示出发点到i点的最短路径数目
    int w[MAXN];//w[i]表示出发点到i点最短路径上救援队总数
    
    int main() {
    	int n,m,c1,c2;//m个城市，n条路 ，c1表示出发点，c2为终点
    	cin>>n>>m>>c1>>c2;
    	for(int i=0; i<n; i++) cin>>weight[i]; //输入每个城市的队伍数量,即点权
    	fill(dis,dis+MAXN,inf);
    	fill(e[0],e[0]+MAXN*MAXN,inf);//初始化
    	int a,b,len;
    	for(int i=0; i<m; i++) {
    		cin>>a>>b>>len;
    		e[a][b]=e[b][a]=len;
    	}
    
    	dis[c1]=0;
    	count[c1]=1;
    	w[c1]=weight[c1];//出发点到自身显然距离为0，路径数为1，最短路径上救援队总数为自身点权
    	for(int i=0; i<n; i++) {
    		int min,u;
    		min=inf;//min为一个比较标准
    		u=-1;//u为剩余点集中距离出发点最短的点，即跳板
    		for(int j=0; j<n; j++) {
    			if(vis[j]==false&&dis[j]<min) {
    				min=dis[j];
    				u=j;
    			}
    		}
    		if(u==-1) break;
    		vis[u]=true;
    		for(int v=0; v<n; v++) {
    			if(vis[v]==false&&e[u][v]!=inf) {
    				if(dis[u]+e[u][v]<dis[v]) { //如果新路径长度小于老路径
    					dis[v]=dis[u]+e[u][v];
    					count[v]=count[u];//点v到出发点的最短路径总数与u的相同
    					w[v]=w[u]+weight[v];//点i到出发点最短路径上救援队总数等于点i的点权加上w[u]
    				} else if(dis[u]+e[u][v]==dis[v]) { //如果新路径长度等于老路径
    					count[v]=count[v]+count[u];//v到出发点的最短路径总数与u到出发点的最短路径总数相加
    					if(w[u]+weight[v]>w[v])//若新路径上的救援队总数更多，则更新为新路径的
    						w[v]=w[u]+weight[v];
    				}
    			}
    		}
    	}
    	cout<<count[c2]<<" "<<w[c2];
    	return 0;
    }