共计 2068 个字符，预计需要花费 6 分钟才能阅读完成。
题目粗心：
给出 N 个城市，M 条无向边。每个城市中都有肯定数目的救济小组, 所有边的边权均有输出失去, 当初给出终点和起点, 求从终点到起点的最短门路条数以及最短门路上的救济小组数目之和。如果有多条最短门路, 则输入数目之和最大的。
算法思路:
本题须要求解从 C1 到 C2 的最短门路上的相干信息, 那么很天然联想到用 Dijstra 算法，此题基本上算的上是模板题目, 间接套用 Dijstra 算法的具体过程即可, 这里惟一的不同在于存在优化门路的第二标尺, 也即是救济队伍数目。
先交代数据的存储：
这里应用 node_weight[1000]示意每一个城市的救济的团队数目，G1000 代表每一条路的长度，dis[1000]示意终点 C1 到所有点的最短距离，visited[1000]为标记拜访数组，num[1000]为终点到起点最优门路的条数，rescue_teams[1000]为终点到起点最优门路上能够携带的最多营救团队数目
Dijkstra 过程：
初始化 dis[C1] = 0;rescue_teams[C1] = node_weight[C1];num[C1] = 1; 而后遍历 N 次，每次首先寻找到一个没有拜访且间隔终点最短的结点 nearest, 而后依据 nearest 结点优化整个图中终点到其余所有节点 (没有拜访) 的最短距离, 当通过 nearest 能够更短的达到 j 时，咱们更新最短距离dis[j],num[j],rescue_teams[j], 当间隔相等时先更新门路条数num[j], 而后判断通过 nearest 到 j 的点权是否更大, 如果是更新最大点权rescue_teams[j], 这里得留神, 门路条数 num 只和最短距离无关.
留神点：
- 1、门路条数 num 只和最短距离无关，在依据点权作为第二约束条件的时候，无需依据点权来更新。
提交后果：
AC 代码：
#include <cstdio>
#include <algorithm>
using namespace std;
int N,M,C1,C2;// 城市数目，路线数目，所在城市，指标城市
int node_weight[1000];// 点权，示意每一个城市的救济的团队数目
int G[1000][1000];// 边权，代表每一条路的长度
int dis[1000];// 终点 C1 到所有点的最短距离
bool visited[1000];// 标记拜访数组
int num[1000];// 最优门路的条数
int rescue_teams[1000];// 最多营救团队数目
void Dijkstra(){fill(dis,dis+1000,0x3fffffff);
dis[C1] = 0;// 终点到终点的最短距离
num[C1] = 1;// 初始门路条数为 1,C1 到本身为一条门路
rescue_teams[C1] = node_weight[C1];// 初始门路的点权之和为 C1 的点权
// 循环 N 次
for (int i = 0; i < N; ++i) {
// 首先找到一个间隔 C1 最近的未拜访的节点
int nearest = -1,min_dis = 0x3fffffff;
for (int j = 0; j < N; ++j) {if(!visited[j]&&min_dis>dis[j]){
nearest = j;
min_dis = dis[j];
}
}
// 没有找到，阐明前面的点不在连通
if(min_dis==0x3fffffff) return;
// 找到间隔 C1 最近的点了，依据 nearest 更新 C1 到其余未拜访的点的间隔
visited[nearest] = true;
for(int j=0;j<N;++j){if(!visited[j]&&G[nearest][j]!=0){if(dis[j]>dis[nearest]+G[nearest][j]){dis[j] = dis[nearest]+G[nearest][j];
num[j] = num[nearest];
rescue_teams[j] = rescue_teams[nearest] + node_weight[j];
} else if(dis[j]==dis[nearest]+G[nearest][j]){
// 门路长度雷同，然而携带的救济团队更多
num[j] += num[nearest];
if(rescue_teams[j]<rescue_teams[nearest]+node_weight[j]){rescue_teams[j] = rescue_teams[nearest] + node_weight[j];
}
}
}
}
}
}
int main()
{scanf("%d %d %d %d",&N,&M,&C1,&C2);
for (int i = 0; i < N; ++i) {scanf("%d",&node_weight[i]);
}
for(int i=0;i<M;++i){
int a,b,length;
scanf("%d %d %d",&a,&b,&length);
G[a][b] = G[b][a] = length;
}
Dijkstra();
printf("%d %d",num[C2],rescue_teams[C2]);
return 0;
}
正文完
