【1003】Emergency (25 分)

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<math.h>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<algorithm> 
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<queue> 
     
    
   

    

     

    
    

     

      using namespace std;  
     
    
   

    

     

    
    

     

      //在dij基础上增加w[]和num[]数组
     
    
   

    

     

    
    

     

      //w[u]表示从起点s到达顶点u可以得到的最大点权之和
     
    
   

    

     

    
    

     

      //num[u]表示从起点s到达顶点u的最短路径条数
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      const int MAXV=510; //最大顶点数
     
    
   

    

     

    
    

     

      const int INF=1000000000; //无穷大
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      //n为顶点数，m为边数，st和ed分别为起点和终点
     
    
   

    

     

    
    

     

      //G为邻接矩阵，weight为点权
     
    
   

    

     

    
    

     

      //d[]记录最短距离，w[]记录最大点权之和，num[]记录最短路径条数
     
    
   

    

     

    
    

     

      int n,m,st,ed,G[MAXV][MAXV],weight[MAXV];
     
    
   

    

     

    
    

     

      int d[MAXV],w[MAXV],num[MAXV];
     
    
   

    

     

    
    

     

      bool vis[MAXV]={false};//vis[i]==true表示顶点i已访问,初值均为false
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void Dijkstra(int s){  //s为起点
     
    
   

    

     

    
    

     
	fill(d,d+MAXV,INF);
     
    
   

    

     

    
    

     
	memset(num,0,sizeof(num));
     
    
   

    

     

    
    

     
	memset(w,0,sizeof(w));
     
    
   

    

     

    
    

     

      	d[s]=0;
     
    
   

    

     

    
    

     

      	w[s]=weight[s];
     
    
   

    

     

    
    

     

      	num[s]=1;
     
    
   

    

     

    
    

     
	for(int i=0;i<n;i++){ //循环n次
     
    
   

    

     

    
    

     
		int u=-1,MIN=INF; //u使d[u]最小,MIN存放该最小的d[u]
     
    
   

    

     

    
    

     
		for(int j=0;j<n;j++){ //找到未访问的顶点中d[]中最小的
     
    
   

    

     

    
    

     
			if(vis[j] == false && d[j] < MIN){
     
    
   

    

     

    
    

     

      				u=j;
     
    
   

    

     

    
    

     

      				MIN=d[j];
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     
		//找不到小于INF的d[u]说明剩下的顶点和起点s不连通
     
    
   

    

     

    
    

     
		if(u == -1) return ;
     
    
   

    

     

    
    

     

      		vis[u]=true; //标记u为已访问
     
    
   

    

     

    
    

     
		for(int v=0;v<n;v++){ 
     
    
   

    

     

    
    

     
			//如果v未访问 && u能到达v && 以u为中介点可以使d[v]更优
     
    
   

    

     

    
    

     
			if(vis[v]==false && G[u][v] != INF){
     
    
   

    

     

    
    

     
				if(d[u]+G[u][v] < d[v]) {  //以u为中介点时能令d[v]变小
     
    
   

    

     

    
    

     

      					d[v]=d[u]+G[u][v]; //覆盖d[v]
     
    
   

    

     

    
    

     

      					w[v]=w[u]+weight[v]; //覆盖w[v]
     
    
   

    

     

    
    

     

      					num[v]=num[u]; //覆盖num[v]
     
    
   

    

     

    
    

     

      				}else if(d[u] + G[u][v] ==d[v]){  //找到一条相同长度的路径
     
    
   

    

     

    
    

     
					if(w[u]+weight[v] > w[v]){  //以u为中介点时点权之和更大
     
    
   

    

     

    
    

     

      						w[v]=w[u]+weight[v]; //w[v]继承自w[u]
     
    
   

    

     

    
    

     

      					}
     
    
   

    

     

    
    

     
					//最短路径条数与点权无关，必须写在外面
     
    
   

    

     

    
    

     

      					num[v] += num[u];
     
    
   

    

     

    
    

     

      				}
     
    
   

    

     

    
    

     

      			}
     
    
   

    

     

    
    

     

      		}
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main(){   
     
    
   

    

     

    
    

     
	scanf("%d%d%d%d",&n,&m,&st,&ed);
     
    
   

    

     

    
    

     
	for(int i=0;i<n;i++){
     
    
   

    

     

    
    

     
		scanf("%d",&weight[i]); //读入点权
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	int u,v;
     
    
   

    

     

    
    

     
	fill(G[0],G[0]+MAXV*MAXV,INF); //初始化图G
     
    
   

    

     

    
    

     
	for(int i=0;i<m;i++){ 
     
    
   

    

     

    
    

     
		scanf("%d%d",&u,&v); //边u--》v
     
    
   

    

     

    
    

     
		scanf("%d",&G[u][v]); //读入边权
     
    
   

    

     

    
    

     

      		G[v][u]=G[u][v]; //因为是无向图
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	Dijkstra(st); //Dijkstra算法入口
     
    
   

    

     

    
    

     
	printf("%d %d\n",num[ed],w[ed]); //最短距离条数，最短路径中的最大点权
     
    
   

    

     

    
    

     
	system("pause");
     
    
   

    

     

    
    

     
    return 0;   
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/99683751