核心是Dijkstra算法。为了做这道题，重新学习了图和广度优先遍历（本来就没学好），邓书上的代码不适合用来做题，Dijkstra算法我还是看别人的博客学的。这题做了收获很大，我参考别人的博客总结了自己的图模板，美滋滋。我觉得邓书上的代码风格很好，别人的建图过程和邓老师的不太一样，虽然殊途同归，但我已经习惯了邓书了...很难看进去别人的建图过程。这题用的Dijkstra算法复杂度还能提高，得用到优先级队列实现，有空再学一下。

这题需要注意：

1.边要设置成双向的，测试点2和5就是测的这一点。

2.在原有的Dijkstra算法的基础上，根据题意设置num和sum数组，具体定义如代码注释所示。

 

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<vector>
  4 #include<queue> 
  5 #include<algorithm>
  6 #define inf 0x3f3f3f3f
  7 using namespace std;
  8 struct Vertex{
  9     int data;
 10     Vertex(int d=0):data(d){}
 11 };
 12 struct Edge{
 13     int weight;
 14     int nextPos;
 15     Edge(){}
 16 };
 17 struct Gragh{
 18     vector<Vertex> V;
 19     vector<vector<Edge> > E;
 20     Gragh(){}    
 21 };
 22  
 23 int main(){  
 24            int VertexNum,EdgeNum,S1,S2;
 25               scanf("%d%d%d%d",&VertexNum,&EdgeNum,&S1,&S2);
 26               
 27               Gragh gragh;
 28               int m;
 29               Vertex vertex;
 30               vector<Edge> empty_e; 
 31         for(int i=0;i<VertexNum;i++){
 32             scanf("%d",&m);
 33             vertex.data=m;
 34             gragh.V.push_back(vertex);
 35             gragh.E.push_back(empty_e);
 36         }
 37         
 38         int C1,C2,L;
 39         Edge edge;
 40         for(int i=0;i<EdgeNum;i++){
 41             scanf("%d%d%d",&C1,&C2,&L);
 42             edge.weight=L;
 43             edge.nextPos=C2;
 44             gragh.E[C1].push_back(edge);
 45             edge.nextPos=C1;//建立无向图哦
 46             gragh.E[C2].push_back(edge);
 47             
 48         }
 49         //至此，图建立完毕
 50         
 51         int visited[VertexNum]={0} ;
 52         int dis[VertexNum];
 53         fill(dis,dis+VertexNum,inf);
 54         dis[S1]=0;
 55         int prev[VertexNum];
 56         fill(prev,prev+VertexNum,-1);
 57            int u,min;
 58            
 59            int num[VertexNum]={0};//num[i]是从出发点到i结点最短路径的条数 
 60            int sum[VertexNum]={0};//sum[i]是从出发点到i结点救援队的数目之和 
 61            num[S1]=1; 
 62            sum[S1]=gragh.V[S1].data;
 63            for(int i=0;i<VertexNum;i++){
 64                
 65                min=inf;
 66                for(int j=0;j<VertexNum;j++){
 67                    if(!visited[j]&&dis[j]<min){
 68                     min=dis[j];
 69                     u=j;
 70                 } 
 71            }
 72             visited[u]=1;//第u个节点的最短路径已经确定 
 73             
 74             for(int j=0;j<gragh.E[u].size();j++){
 75                    int v=gragh.E[u][j].nextPos;
 76                    if(!visited[v]){
 77                        if(dis[u]+gragh.E[u][j].weight<dis[v]){
 78                            dis[v]=dis[u]+gragh.E[u][j].weight;
 79                            prev[v]=u;
 80                            num[v]=num[u];//继承u的最短路径条数 
 81                            sum[v]=gragh.V[v].data+sum[u];//更新sum[v] 
 82                           }
 83                           else if(dis[u]+gragh.E[u][j].weight==dis[v]){
 84                               num[v]=num[v]+num[u];
 85                               if(sum[v]<sum[u]+gragh.V[v].data)
 86                                 sum[v]=sum[u]+gragh.V[v].data;
 87                               
 88                           }
 89                    }
 90                }
 91                
 92            }
 93            
 94         printf("%d %d",num[S2],sum[S2]); 
 95            
 96            
 97         
 98     
 99 return 0;
100 }