优化后的文章内容

题目链接

https://pintia.cn/problem-sets/994805046380707840/problems/994805073643683840

题意

给定n个城市和m条边，每个城市都有一定数量的救援队。要求从起点s到终点d的最短路径，同时确保路上尽可能多地召集救援队。

思路

这是一个结合最短路径和救援队召集的复杂问题。我们可以使用优化后的Dijkstra算法来解决这个问题。为了实现这一目标，我们在传统的最短路径问题上增加了一维，表示每个城市可以召集的救援队数量。此外，我们还需要记录最短路径的数量以及路径的前驱节点，以便在找到最短路径后，能够回溯路径并输出结果。

AC代码

#include 
   
    using namespace std;const int INF = 0x3F3F3F3F;int n, m, s, d;int a[505][505], jyd[505], pre[505], dis[505], num[505], vis[505], ct[505];void dijkstra() {    dis[s] = 0;    pre[s] = -1;    num[s] = jyd[s];    vis[s] = 1;    ct[s] = 1;    while (1) {        int min = INF, k;        for (int i = 0; i < n; ++i) {            if (!vis[i] && dis[i] < min) {                min = dis[i];                k = i;            }        }        if (k == d || min == INF) break;        vis[k] = 1;        for (int i = 0; i < n; ++i) {            if (!vis[i] && dis[i] > dis[k] + a[k][i]) {                dis[i] = dis[k] + a[k][i];                num[i] = num[k] + jyd[i];                ct[i] = ct[k];                pre[i] = k;            } else if (!vis[i] && dis[i] == dis[k] + a[k][i]) {                ct[i] += ct[k];                if (num[i] < num[k] + jyd[i]) {                    num[i] = num[k] + jyd[i];                    pre[i] = k;                }            }        }    }}void print(int p) {    if (p == 0) {        print(pre[p]);        if (p == s) {            printf("%d", p);        } else {            printf(" %d", p);        }    }}int main() {    scanf("%d%d%d%d", &n, &m, &s, &d);    for (int i = 0; i < n; ++i) {        for (int j = 0; j < n; ++j) {            scanf("%d", &a[i][j]);        }    }    dijkstra();    print(d);}

代码解释

变量定义：包括常量INF和数组a、jyd等，用于存储边的权重和各城市的救援队数量。

Dijkstra算法：

初始化距离数组dis，记录当前节点的距离，起点s的距离为0。

使用优先队列（通过循环实现）进行最短路径搜索。

对于每个节点，更新其邻居节点的距离、救援队数量和路径记录。

路径记录：

使用数组pre记录路径的前驱节点。

使用数组ct记录到达每个节点的最短路径的数量。

使用数组num记录到达每个节点的救援队总数。

打印路径：通过递归函数print回溯路径并输出。

这个解决方案不仅能找到从起点到终点的最短路径，还能确保路径上尽可能多地召集救援队。

转载地址：http://pwafk.baihongyu.com/

你可能感兴趣的文章