【1003】Emergency (25 分)

举报
野猪佩奇996 发表于 2022/01/23 01:17:10 2022/01/23
【摘要】 #include<iostream>#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#include<algorithm> #include<map>#inclu...

      #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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。