PAT原題鏈接： 傳送門
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 c?1, 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
題目大意
題目給出n個城市有m條邊使得每兩個城市有一條道路相連估灿，每條邊有著相應的長度，城市編號由0~n-1簿晓，起初每個城市都有一定人數的救援隊帽借，現在給出一個出發(fā)點c1和終點c2晚唇，終點發(fā)生火災后要求你帶領出發(fā)點的救援隊出發(fā)救援，沿途召集你經過的城市的救援隊參與救援，要求路程盡可能的短萤衰，同時如果有多條路一樣短則記錄下這樣的路總數有幾條艰争，同時記錄下這幾條最短的路中你可以沿途召集到的盡可能多的救援隊的數量坏瞄，輸出最短路徑數和最多可召集的救援隊數量
題目分析
典型的求一固定點到其他任意點的最短路徑問題，通過dijkstra算法求從c1出發(fā)到其他點的最短路徑园细，從c1出發(fā)初始化c1到自己的路徑長度為0惦积，其余為無窮大，在dist數組中保存從c1點出發(fā)到其他各點的最短路徑猛频，循環(huán)n-1次狮崩，每次從中選擇一個未走過的最短點，作為下一個要走的點鹿寻，因為已經將c1到達自己的距離設置為0睦柴，所以第一次選擇的dist[c1]的點，代表從c1出發(fā)毡熏，和題意相合（設置man數組放置每個點初始有的救援隊坦敌，num數組放置到達某個點的最短路徑的數量，peo放置到達某個點的最多的救援隊）
在具體選擇出下一個點k之后痢法，遍歷通過該點k是否會使得從c1出發(fā)到達其他點j的最短路徑縮小狱窘，判斷可以走之后，還有兩種可能性：
- 到j點路徑長度縮小 因為j是通過k到達的财搁，所以到j的走法num[j]=num[k]蘸炸，j的救援隊最多是peo[k]+j點原來的人數
- 到j點路徑長度不變 那么j可以通過k到達，也可以不通過尖奔，num[j]+=num[k],j的救援隊最多為max(peo[j],peo[k]+man[j]),通過k到j的人多還是通過別的走法到j的人多搭儒，取一個大的值即可
本題代碼
#include<iostream>
#include<algorithm>
#include<string>
#include<cstdio>
#include<queue>
#include<string.h>
#include<cmath>
using namespace std;
const int N=505;
const int M=0x3f3f3f3f;//存放最大值
int vis[N];//是否走過的點
int mat[N][N];//兩點之間的距離
int man[N];//某地初始時救援隊的數量
int dist[N];//從c1出發(fā)到其他地的最短路徑
int num[N];//c1到其他點的最短路徑的條數
int peo[N];//c1到其他點可召集的救援隊數量，在最短路徑的基礎上
int n,m,c1,c2;
int main(){
scanf("%d%d%d%d",&n,&m,&c1,&c2);
for(int i=0;i<n;i++)
scanf("%d",&man[i]);
//初始化
memset(dist,M,sizeof(dist));
memset(mat,M,sizeof(mat));
dist[c1]=0;
mat[c1][c1]=0;
// memset(vis,0,sizeof(vis));
// memset(num,0,sizeof(num));
// memset(peo,0,sizeof(peo));
num[c1]=1; //到達起始點的最短路徑初始化為1條
peo[c1]=man[c1]; //到達起始點的人數最多為man[c1]
int a,b,c;
for(int i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
mat[a][b]=c;
mat[b][a]=c;
}
// for(int i=0;i<n;i++)
// dist[i]=mat[c1][i];
for(int i=1;i<n;i++){
int minn=M;
int k=-1;
for(int j=0;j<n;j++){
if(vis[j]==0&&dist[j]<minn){
minn=dist[j];
k=j;
}
}
if(k==-1) break; //剩下的道路已經不通
vis[k]=1;
for(int j=0;j<n;j++){
if(vis[j]==0&&dist[k]+mat[k][j]<M&&dist[k]+mat[k][j]<dist[j]){
//有更短的路徑
dist[j]=dist[k]+mat[k][j];
num[j]=num[k];
peo[j]=peo[k]+man[j];
}
else if(vis[j]==0&&dist[k]+mat[k][j]<M&&dist[k]+mat[k][j]==dist[j]){ //此處的else if開始用成了if
num[j]+=num[k];
peo[j]=max(peo[j],peo[k]+man[j]);
}
}
}
printf("%d %d\n",num[c2],peo[c2]);
return 0;
}
