【1003】Emergency (25 分)
【摘要】
#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)