Pat甲级 1003 Emergency (25分)

1.比较重要的单词的含义

• emergency n.紧急情况，adj.紧急的
• rescue v.营救
• scatter v.分散
• amount n.数量，总数
• at the mean time 同时
• call up 召集
• positive adj.正的
• currently adv.当前，目前
• guarantee v.保证
• maximum adj.最多的
• gather v.聚集
• exactly adv.恰好地

2.解题思路

这题用图的深度优先遍历就可以实现，比较简单，代码如下：

#include <iostream>
using namespace std;

int dsp = 1;//shortest paths
int dspNums = 0;//the number of different shortest paths
int maxt = 0;//the maximum amount of rescue teams
int u[501][501] = {0};//邻接矩阵

void DFS(int len,int *v,int *rt,int c1,int c2,int roadLen,int rtNum,int row,int rtn){
  int vv[len];
  for(int i = 0;i < len;i++){
      vv[i] = v[i];
  }
  roadLen = roadLen + row;//加上路径长度
  rtNum = rtNum + rtn;//加上救援队个数
  vv[c1] = 1;//将参观状态置为1
  if(c1 == c2){    
         //到达终点，进行统计最小路径与救援队个数
         if(roadLen < dsp){
             dsp = roadLen;
             dspNums = 1;
             maxt = rtNum;               
         }else if(roadLen == dsp){
             dspNums++;
             if(rtNum > maxt){
                 maxt = rtNum;
             }             
         }
      return;
   }
  for(int i = 0;i < len;i++){
      if(u[c1][i] == 0){
          continue;
      }else{          
          if(vv[i] == 1){
                //已经参观过了
                continue;                
          }else{
              //还没参观
              row = u[c1][i];//路径长度
              rtn = rt[i];//救援队个数              
              DFS(len,vv,rt,i,c2,roadLen,rtNum,row,rtn);//前去参观
          }
     }
  }   
}

int main(){
  int n,m,c1,c2;
  cin>>n>>m>>c1>>c2;
  int resure_t[n];//救援队数目
  for(int i = 0;i < n;i++){
      cin>>resure_t[i];
  }
  for(int i = 0;i < m;i++){
      int a;//城市c1序号
      int b;//城市c2序号
      int len;//路径长度
      cin>>a>>b>>len;
      u[a][b] = len;
      u[b][a] = len;
      dsp = dsp + len;
  } 
  int v[n] = {0};  
  DFS(n,v,resure_t,c1,c2,0,resure_t[c1],0,0);
  cout<<dspNums<<" "<<maxt;
  return 0;
}