杭州市的公共自行车系统为游客提供了极大的便利，允许用户在任意站点借车并在其他站点还车。

公共自行车管理中心（PBMC）需要实时监控所有站点的自行车容量。当一个站点的自行车数量正好是其最大容量的一半时，该站点被认为是处于"完美"状态。如果站点为空或已满，PBMC会进行干预，通过调配自行车来使其恢复到完美状态，同时也会调整沿途经过的站点。

当需要解决一个问题站点时，PBMC总是选择最短路径前往。若存在多条最短路径，则优先选择需要PBMC运送最少自行车的路径。

以下图为例：站点表示为节点，道路表示为边，边上的数字代表通行时间。节点内的数字表示当前自行车数量，最大容量为10。

解决站点 S3​ 的问题，存在两条最短路径：

1. PBMC → S1​ → S3​。此路径需要PBMC运送4辆自行车。具体操作是：从S1​收集1辆自行车，然后将5辆自行车运往S3​，使两站均达到完美状态。
2. PBMC → S2​ → S3​。此路径与路径1耗时相同，但仅需PBMC运送3辆自行车，因此被选中。

输入格式：

每个输入文件包含一个测试用例。 第一行包含四个整数：Cmax（≤100，偶数），每个站点的最大容量；N（≤500），站点总数；Sp，问题站点的索引（站点编号从1到N，PBMC为0）；以及M，道路数量。 第二行包含N个非负整数Ci（i=1,⋯,N），表示Si​站点的当前自行车数量。 之后M行，每行包含三个整数：Si, Sj, Tij，描述在Si​和Sj​之间移动所需的时间Tij。所有数字之间用空格分隔。

输出格式：

对于每个测试用例，在单行输出结果。首先输出PBMC需要运送的自行车数量，后跟一个空格，然后是路径（格式：0−>S1​−>⋯−>Sp​），最后再跟一个空格，输出调整Sp​站点状态后需要运回PBMC的自行车数量。

注意：如果路径不唯一，输出需要PBMC运送最少自行车的路径。若仍有歧义，则选择运回PBMC的自行车数量最少的路径。题目保证路径唯一。

示例输入：

10 3 3 5
6 7 0
0 1 1
0 2 1
0 3 3
1 3 1
2 3 1

示例输出：

3 0->2->3 0

问题分析

本问题要求找到一条从PBMC（站点0）到目标站点Sp的最短路径，同时最小化从PBMC出发时需要运送的自行车数量。如果有多条最短路径，选择运送自行车数量最少的；若仍有相同数量的最少运送自行车，则选择最终运回PBMC的自行车数量最少的路径。

传统的Dijkstra算法只能找到最短路径，但无法直接处理"最小化运送/运回自行车数量"的约束。这是因为在路径上的"运送"和"运回"行为不具备简单的最优子结构性质，即局部最优（在某一段路径上）不一定能保证全局最优（整个路径）。例如，某段路径可能需要运送更多自行车，但最终可以减少从Sp运回的自行车数量，反之亦然。因此，在确定所有可能的最短路径后，需要进一步的搜索来找到最优解。

一种有效的解决方案是结合Dijkstra算法和深度优先搜索（DFS）。首先，使用Dijkstra算法找出所有到达Sp的最短路径。在Dijkstra算法的松弛操作中，当发现一条等长的最短路径时，需要记录下所有到达该节点的前驱节点。然后，使用DFS从Sp回溯到0，遍历所有最短路径。在DFS过程中，计算每条路径所需的初始运送量和最终运回量，并根据题目要求（先最小化运送量，再最小化运回量）选出最优路径。

在DFS的回溯过程中，可以维护一个变量来表示当前路径上累计的自行车盈亏情况。当站点自行车数量大于Cmax / 2时，表示有盈余，累加到盈亏值；当小于Cmax / 2时，表示有亏损，从盈亏值中减去亏损量。如果亏损量大于当前盈亏值，则需要从PBMC运送自行车来弥补差额，并更新需要运送的总量。同时，在到达Sp时，根据最终的盈亏值计算需要运回PBMC的自行车数量。

代码实现

以下是使用Dijkstra算法结合DFS解决此问题的C++代码示例。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int inf = 99999999; // 定义一个较大的值表示无穷大
int cmax, n, sp, m; // 最大容量, 站点数, 问题站点, 道路数
int minNeed = inf, minBack = inf; // 最小运送量, 最小运回量
int edge[510][510]; // 邻接矩阵存储边权重 (时间)
int distance_val[510]; // 存储从源点到各点的最短距离
int station_balance[510]; // 存储每个站点的自行车数量与完美状态的差值 (weight[i] - cmax/2)
bool visited[510]; // 标记是否已访问
vector<int> predecessors[510]; // 存储每个节点的所有最短路径前驱
vector<int> current_path, best_path; // 当前DFS路径, 最优路径

// DFS函数，用于遍历所有最短路径并寻找最优解
void dfs(int current_station) {
    current_path.push_back(current_station); // 将当前站点加入路径

    // 如果已到达起点PBMC (站点0)
    if (current_station == 0) {
        int bikes_to_send = 0; // 需要从PBMC运送的自行车数量
        int bikes_to_return = 0; // 需要运回PBMC的自行车数量

        // 从终点(Sp)向前回溯计算自行车调配情况
        for (int i = current_path.size() - 1; i >= 0; i--) {
            int station_idx = current_path[i];
            if (station_balance[station_idx] > 0) {
                // 站点有盈余，累加到待运回数量
                bikes_to_return += station_balance[station_idx];
            } else {
                // 站点有亏损
                if (bikes_to_return > -station_balance[station_idx]) {
                    // 运回的自行车足够弥补亏损
                    bikes_to_return += station_balance[station_idx];
                } else {
                    // 运回的自行车不足，需要从PBMC运送
                    bikes_to_send += (-station_balance[station_idx] - bikes_to_return);
                    bikes_to_return = 0; // 运回量清零
                }
            }
        }

        // 更新最优解
        if (bikes_to_send < minNeed) {
            minNeed = bikes_to_send;
            minBack = bikes_to_return;
            best_path = current_path;
        } else if (bikes_to_send == minNeed && bikes_to_return < minBack) {
            minBack = bikes_to_return;
            best_path = current_path;
        }

        current_path.pop_back(); // 回溯，移除当前站点
        return;
    }

    // 递归调用DFS，遍历所有前驱节点
    for (int i = 0; i < predecessors[current_station].size(); i++) {
        dfs(predecessors[current_station][i]);
    }

    current_path.pop_back(); // 回溯，移除当前站点
}

int main() {
    // 初始化邻接矩阵为无穷大
    fill(edge[0], edge[0] + 510 * 510, inf);
    // 初始化距离数组为无穷大
    fill(distance_val, distance_val + 510, inf);

    scanf("%d%d%d%d", &cmax, &n, &sp, &m);

    // 读取各站点自行车数量，并计算与完美状态的差值
    for (int i = 1; i <= n; i++) {
        int current_bikes;
        scanf("%d", ¤t_bikes);
        station_balance[i] = current_bikes - cmax / 2;
    }

    // 读取道路信息，构建邻接矩阵
    for (int i = 0; i < m; i++) {
        int u, v, time;
        scanf("%d%d%d", &u, &v, &time);
        edge[u][v] = edge[v][u] = time; // 无向图
    }

    distance_val[0] = 0; // PBMC到自身的距离为0

    // Dijkstra算法寻找最短路径
    for (int i = 0; i <= n; i++) {
        int u = -1, min_dist = inf;
        // 找到未访问节点中距离最小的节点
        for (int j = 0; j <= n; j++) {
            if (!visited[j] && distance_val[j] < min_dist) {
                u = j;
                min_dist = distance_val[j];
            }
        }

        if (u == -1) break; // 所有可达节点已访问
        visited[u] = true; // 标记为已访问

        // 更新相邻节点距离
        for (int v = 0; v <= n; v++) {
            if (!visited[v] && edge[u][v] != inf) {
                if (distance_val[v] > distance_val[u] + edge[u][v]) {
                    // 发现更短路径，更新距离并清空前驱
                    distance_val[v] = distance_val[u] + edge[u][v];
                    predecessors[v].clear();
                    predecessors[v].push_back(u);
                } else if (distance_val[v] == distance_val[u] + edge[u][v]) {
                    // 发现等长最短路径，添加前驱
                    predecessors[v].push_back(u);
                }
            }
        }
    }

    // 从问题站点Sp开始DFS寻找最优路径
    dfs(sp);

    // 输出结果
    printf("%d 0", minNeed);
    // 逆序打印路径 (因为DFS存储的是从Sp到0，需要反转)
    for (int i = best_path.size() - 2; i >= 0; i--) {
        printf("->%d", best_path[i]);
    }
    printf(" %d\n", minBack);

    return 0;
}