PAT (Advanced Level)——1003 Emergency (25分)

小咪咪 2023-06-23 13:28 13阅读 0赞

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

小技巧：正无穷赋值为 0x3f3f3f3f

题意：给你一个无向图，存在环，每个点都有一个权值，代表这个城市的救援人员的人数，问你从C1到C2的最短的路径有多少条，这些最短路径所经过的城市救援人员的人数总和最多是多少。

分析：一看就是最短路的题目，该题存在环，spfa不能用，利用dijstra算法。  
我们先看需要维护啥，不用说，最短路径dis数组要维护，题目还要求最短路径的条数和经过城市的总人数，再维护num数组和w数组分别代表最短路径的条数和经过城市的总人数。

思想：每次找离起始点最近的点进行松弛，dis\[C1\]=0,num\[C1\]=1,w\[C1\]=weight\[C1\]。从C1开始松弛，

找到新的最短路：  
if（dis\[v\]>dis\[u\]+mp\[u\]\[v\] ） 进行dis\[v\]>dis\[u\]+mp\[u\]\[v\]松弛 ，说明有更短的路可以选择；num\[v\]=num\[u\]， v城市由u城市更新过来的，最短路的条数也就是u城市的条数，因为u城市到v城市的路只有1条，C1点到u城市有num\[u\]条；w\[v\]=w\[u\]+weight\[v\],很容易理解，v城市的人数就是更新来的u城市的人数+本城市的人数。

找到与最短路路径一样的路  
else if（dis\[v\]==dis\[u\]+mp\[u\]\[v\] ）  
我们只需要更新num数组和w数组，num\[v\]=num\[v\]+num\[u\],表示一个新的城市u到达v城市有num\[u\]条，之前v城市还有num\[v\]条，求和就是到达v城市的最短路的总条数。有人可能会觉得重复： 答：dij每次都是找一个距离原点最近的点，每次找到后松弛完都会被标记掉，下次不会选它，而这次找到的城市u就是新找到的点，不会与之前的路径重复；w数组求一个最大值就行。

## 反思： ##

思维不要固定为模板，深入理解算法的本质，在这个题中我先把C1给标记为1了，导致num数组和w数组没法更新。之前的模板只有1个dis数组，先预处理dis\[i\]=mp\[c1\]\[i\] ,所以把C1给标记掉，本题不用预处理dis，直接dis\[C1\]=0，其他赋值负无穷，找第一个最小的点就是C1，在第一次松弛的时候就是之前模板的预处理dis数组。

还是没彻底理解算法的思想，以后要注意这方面的复习，要不有模板也不会改。

#include<iostream>
    #include<algorithm>
    #include<cstring>
    using namespace std;
    typedef long long ll;
    const ll inf=0x3f3f3f3f;
    const int maxn=505;
    ll mp[maxn][maxn],dis[maxn],weight[maxn];
    ll n;
    ll book[maxn],w[maxn],num[maxn];
    void init(ll n)
    { 
    	for(int i=1;i<=n;i++)
    	{ 
    		dis[i]=inf;
    		for(int j=1;j<=n;j++)
    		{ 
    			if(i!=j)
    				mp[i][j]=inf;
    			else
    				mp[i][j]=0;
    		}
    	 } 
     } 
    int main()
    { 
    	ll m,c1,c2,u,nn;
    	cin>>n>>m>>c1>>c2;
    	c1++,c2++;
    	init(n);
    	for(int i=1;i<=n;i++)
    	{ 
    		cin>>weight[i];
    	} 
    	w[c1]=weight[c1];
    	num[c1]=1;
    	dis[c1]=0;	
    	for(int i=1;i<=m;i++)
    	{ 
    		ll s,e,d;
    		cin>>s>>e>>d;
    		s++;
    		e++;
    		mp[s][e]=mp[e][s]=d;
    	}
    	//book[c1]=1;//没理解算法思想 
    	for(int i=1;i<=n;i++)
    	{  
    		nn=inf;
    		u=-1;
    		for(int j=1;j<=n;j++)
    		{ 
    			if(book[j]==0&&dis[j]<nn)
    			{ 
    				nn=dis[j];
    				u=j;
    			}
    		}
    		if(u==-1)
    			break;
    		else
    			book[u]=1;
    		for(int v=1;v<=n;v++)
    		{ 
    			if(book[v]==0&&mp[u][v]!=inf)
    			{ 
    				if(dis[v]>dis[u]+mp[u][v])
    				{ 
    					dis[v]=dis[u]+mp[u][v];
    					num[v]=num[u];
    					w[v]=w[u]+weight[v];
    				}
    				else if(dis[v]==dis[u]+mp[u][v])
    				{ 
    					num[v]+=num[u];
    					if(w[v]<w[u]+weight[v])
    						w[v]=w[u]+weight[v];
    				}
    			}
    		}
    	}
    	cout<<num[c2]<<" "<<w[c2]<<endl;
    	return 0;
    }