一、题目
image.png
image.png
二、注意
- dijkstra
- dijkstra算法的实现
- 解决已选元素集合s， bool vis[n]
- 解决起点到各顶点最短路径，int d[n]
- 解决最短路径的条数，int num[n]
- 解决最短路径的最大顶点权值之和，int w[n]
- 如何输出最短路径（当最短路径唯一时）
#include <algorithm>
//使用fill，给数组赋初始值
//1. fill(首地址，终地址，初值)
//2. 一维数组int A[n]的首地址为：A
//3. 二维数组int A[n][n]的首地址为：A[0]，同样也是第一行的首地址
int num[MAXV]; //最短路径的条数
fill(num, num + MAXV,0);
- dijkstra的变体问题：碰到有两条及以上可以到达最短距离的路径，存在两个尺度：第一个尺度——距离；第二个尺度——可以是边权（花费）、点权等。要求在最短路径中，也就是选择在第一个尺度的基础上，使得第二个尺度的最优的一条路径。常见的第二尺度如下：
- 给每条边增加一个边权（花费），然后要求在最短路径的有多时要求路径上的花费之和最小
- 给每个点增加一个点权（例如每个城市能收集到的物资），然后在最短路径有多条时要求路径上的点权之和最大
- 直接询问有多少条最短路径
- 单词：
- the number of different shortest paths between C1 and C2: C1到C2之间最短路径的条数
- the maximum amount of rescue teams you can possibly gather：你可以获得的最大营救队的数量
- scattered: 分散的
- call up as many hands on the way as possible: 在这条路上召集尽可能多的人
三、思路代码
#include <iostream>
#include <algorithm>
//使用fill，给数组赋初始值
//1. fill(首地址，终地址，初值)
//2. 一维数组int A[n]的首地址为：A
//3. 二维数组int A[n][n]的首地址为：A[0]，同样也是第一行的首地址
using namespace std;
const int MAXV = 500; //顶点数最大值
const int INF = 1000000; //最大值
int N;//城市数量
int M;//路径的数量，边的数量
int C1,C2;//所在城市和目标城市
int G[MAXV][MAXV];//图
int teams[MAXV];//点权
int d[MAXV]; //最短路径
int w[MAXV]; //最大的权值之和, the maximum amount of rescue teams
int num[MAXV]; //最短路径的条数，the number of different shortest paths between C1 and C2
bool vis[MAXV] = {false}; //标记访问数组
//单源最短路径，dijskra算法
void Dijkstra(int s) //G为邻接矩阵存储的无向图的结构，C1为起点,C2为终点，N为城市数量
{
//初始化，最短路径数组，最短路径数量数组，最大点权和数组
fill(d,d+MAXV,INF);
d[s] = 0; //起点到自身的距离为0
fill(num, num + MAXV,0);
fill(w,w + MAXV,0);
w[s] = teams[s]; //自己到自己的最短路径点权和最大就是自己的点权值
num[s] = 1; //到自身的路径至少有1条，且为最短
for(int i=0;i<N;i++) //循环N次，依次访问N个节点
{
int u = -1;
int MIN = INF;
for(int j=0;j<N;j++)
{
if(vis[j]==false&&d[j]<MIN) //如果节点j未被访问过，并且起点到节点j的新距离小于MIN，更新MIN
{
u=j;
MIN = d[j];
}
}
//找不到小于max的d[u],说明剩下的顶点与起点s不连通
if(u==-1)
return;
vis[u]=true; //标记已经访问过
//判断新加入的节点u对num[] w[] d[]造成的影响
for(int v=0;v<N;v++)
{
if(vis[v]==false && G[u][v]!=INF) //v点未被访问，且u和v之间存边
{
if(d[u]+G[u][v]<d[v]) //路径更优
{
d[v] = d[u]+G[u][v]; //更新更优路径
w[v] = w[u]+teams[v]; //在u点权值和的基础上+v点权值
num[v] = num[u]; //有多少条到u的路径，那么就有多少条到v的路径，因为u->v
}else if(d[u]+G[u][v] == d[v]){ //找到一条相长度的路径
if(w[u] + teams[v] > w[v])
w[v] = w[u]+teams[v];
num[v] += num[u]; //新增一条路径
}
}
}
}
}
int main()
{
cin >>N>>M>>C1>>C2; //输入
fill(teams,teams+MAXV,0);//救援队数量
for(int i=0;i<N;i++)
{
cin >>teams[i];
}
fill(G[0],G[0]+MAXV*MAXV,INF); //城市之间的道路的长度初始化为无穷大
for(int i=0;i<M;i++) //输入构造图
{
int a,b,c;
cin>>a>>b>>c; //a->b的长度为c
G[a][b] = c; //读入边的权值
G[b][a] = c;
}
Dijkstra(C1); //求出源点C1到C2的最短路径条数，在最短路径的基础上可以获得的最多的救援队数量
cout <<num[C2]<<" "<<w[C2];
return 0;
}
