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
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
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 题目大意：给出n个城市，m条道路，抢修队所在起始点c1和目的抢修节点c2接下来给出n个城市的内各节点的抢修队伍数
m个二端城市以及道路长度
求最短路径数和多条相同最短路径的节点的抢修队伍数和最大值
解题法二种：（1）Dijkstra：在最短路径相等时进行判断。
#include<iostream> #include<cstring> using namespace std; const int maxsize=501; int visit[maxsize]; int teams[maxsize]; int amount[maxsize]; int pathcount[maxsize]; int dist[maxsize]; int edges[maxsize][maxsize]; const int INF=0x7f7f7f7f; void Dijkstra(int from,int to,int n) { amount[from]=teams[from]; pathcount[from]=1; dist[from]=0;//这样处理是让第一次选择出开始节点c1 for(int j=0;j<n;++j)//while(true) { int u,dmin=INF; for(int i=0;i<n;++i) { if(visit[i]==0 && dist[i]<dmin) { dmin=dist[i]; u=i; } } //(dmin==INF || u==to) // break; visit[u]=1; for(int i=0;i<n;++i) { if(visit[i]==0 && dist[i]>dist[u]+edges[u][i]) { dist[i]=dist[u]+edges[u][i]; amount[i]=amount[u]+teams[i];//抢修队数 pathcount[i]=pathcount[u]; //最短路径不相等的话，路径数等于前一个节点的 } else if(visit[i]==0 && dist[i]==dist[u]+edges[u][i]) { pathcount[i]+=pathcount[u];//另外加上中间节点u到i的路径数 if(amount[i]<amount[u]+teams[i]) amount[i]=amount[u]+teams[i]; } } } } int main() { //freopen("in.txt","r",stdin); int n,m,c1,c2; int i,j; cin>>n>>m>>c1>>c2; for(i=0;i<n;++i) cin>>teams[i]; memset(edges,0x7f,sizeof(edges)); memset(dist,0x7f,sizeof(dist)); for(i=0;i<m;++i) { int from,to,L; cin>>from>>to>>L; edges[from][to]=edges[to][from]=L; } Dijkstra(c1,c2,n); cout<<pathcount[c2]<<" "<<amount[c2]; return 0; }（2）dfs：对目的节点进行判断以及中间节点的给出（看了好久才看懂）
#include<iostream> #include<cstring> using namespace std; int n,m,c1,c2; const int maxsize=502; const int INF=0x7fffffff; int teams[maxsize]; int edges[maxsize][maxsize]; int visit[maxsize]; int dist[maxsize]; int shortNum=0,maxTeam=0,minDist=INF; void dfs(int from,int dis,int team) { if(from==c2)//到达目的节点时递归返回 { if(dis<minDist) { minDist=dis; shortNum=1; maxTeam=team; } else if(dis==minDist) { shortNum++; if(team>maxTeam) maxTeam=team; } return ; } visit[from]=1; for(int i=0;i<n;++i)//开始节点c1到i递归，再从i递归到目的节点c2 { if(visit[i]==0 && edges[from][i]>0) dfs(i,dis+edges[from][i],team+teams[i]); } visit[from]=0;//前面通过中间节点i递归的，访问记录要清除 return ; } int main() { //freopen("in.txt","r",stdin); cin>>n>>m>>c1>>c2; for(int i=0;i<n;++i) cin>>teams[i]; memset(edges,-1,sizeof(edges));//这里初始化成-1是有讲究的 for(int i=0;i<m;++i) { int from,to,L; cin>>from>>to>>L; edges[from][to]=edges[to][from]=L; } dfs(c1,0,teams[c1]); cout<<shortNum<<" "<<maxTeam; return 0; } （2.1）dfs的另一种： #include <cstdio> #include <cstdlib> #include <climits> const int MAX = 501; int wei[MAX],visit[MAX],map[MAX][MAX]; int mind,cnt,maxt,n; void init(int n){ int i,j; for(i=0;i<n;++i){ visit[i] = 0; for(j=0;j<n;++j){ map[i][j]=INT_MAX; } } } void dfs(int p,const int end,int dist,int weit){ if(p==end){ if(dist<mind){ cnt = 1; mind=dist; maxt = weit; }else if(dist==mind){ ++cnt; if(maxt<weit){ maxt = weit; } } return; } int i; if(dist>mind)return;//这个地方不剪枝的话最后一个case过不去 for(i=0;i<n;++i){ if(visit[i]==0 && map[p][i]!=INT_MAX){ visit[i] = 1; dfs(i,end,dist+map[p][i],weit+wei[i]); visit[i] = 0; } } } int main(){ int m,st,end,x,y,d,i; mind = INT_MAX; cnt = 0; scanf("%d %d %d %d",&n,&m,&st,&end); init(n); for(i=0;i<n;++i){ scanf("%d",&wei[i]); } while(m--){ scanf("%d %d %d",&x,&y,&d); if(map[x][y]>d){ map[x][y] = map[y][x] = d; } } dfs(st,end,0,wei[st]); printf("%d %d\n",cnt,maxt); return 0; }