⚠️ Dijkstra + DFS | 路径维护、DFS回溯

1018 Public Bike Management (30 分)

这题看了「算法笔记」才发现细节这么多😭，自己想怕是只能过个样例……

• ⚠️要求在去往目标点的时候，就将沿路结点调整好，而不是折返时还可调整，所以不是简单累加看这条路径上的结点跟完全调整好后的差值就能确定带回、带出的自行车数的。 必须有remain、need两个量，不能仅用一个量的绝对值和正负来记录带去、带回的数量。

• 仅仅Dijkstra是无法解决此题的，dijkstra仅得到了最短路径的走法(可能有多条)。还需要按照前驱结点，从目标结点开始，DFS所有最短路才能确定哪条最短路是需要带去/带回自行车最少的。

• 最短路径可能有多条，用vector<int> pre[MAXN]来记录最短路径上当前结点x的前驱们以便DFS回溯。

• DFS的起点是目标点，终点是源点（PBMC）

• 保存结点数值时，将结点的数值直接减去MaxCapacity的一半，给DFS省点事= =

• 注意结点有nn+1个

When a problem station is reported, PBMC will always choose the shortest path to reach that station.
If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen.
Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge's data guarantee that such a path is unique.

⚠️注释掉的部分是典型错误，因为要求在去往目的点的路上就调整好，而非往返一次调整好；若往返一次调整好，就只需Dijkstra、计数路径上点与perfect conditon的总差值了。

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cmath>

#define INF 0x3fffffff
using namespace std;
int graph[501][501], ori_bikes[501] = {0}, dist[501];
bool visited[501] = {false};
int Capacity, nn, Target, mm, least_need = INF, least_remain = INF;
vector<int> pre[501], path, temp_path;

void Dijkstra(int root) {
    fill(dist, dist + nn + 1, INF);
    dist[root] = 0;
    for (int i = 0; i <= nn; ++i) { // 0 - nn  nn+1
        int min_dist = INF, curr = -1;
        for (int j = 0; j <= nn; ++j) {
            if (!visited[j] && dist[j] < min_dist) {
                curr = j, min_dist = dist[j];
            }
        }
        if (curr != -1) {
            visited[curr] = true;
            for (int j = 0; j <= nn; ++j) {
                if (graph[curr][j] != INF && !visited[j]) {
                    int new_dist = dist[curr] + graph[curr][j];
                    if (new_dist < dist[j]) {
                        dist[j] = new_dist;
                        pre[j].clear();
                        pre[j].emplace_back(curr);
                    } else if (new_dist == dist[j]) {
                        pre[j].emplace_back(curr);
                    }
                }
            }
        } else {
            printf("not reachable!!!\n");
            return;
        }
    }
}

void DFS(int root) {
    temp_path.push_back(root);
    if (root == 0) {
        int size = temp_path.size(), remain = 0, need = 0;
        for (int i = size - 1; i >= 0; i--) {
            int curr = temp_path[i];
            if (ori_bikes[curr] < 0) {
                int _abs = abs(ori_bikes[curr]);
                if (remain > _abs)
                    remain -= _abs;
                else {
                    need += _abs - remain;
                    remain = 0;
                }
            } else if (ori_bikes[curr] > 0) {
                remain += ori_bikes[curr];
                /*
                    if (ori_bikes[curr] > need) {
                        need = 0;
                        remain += (ori_bikes[curr] - need);
                    } else {
                        need -= ori_bikes[curr];
                    }
                 */
            }
        }
        if (need < least_need) {
            path = temp_path;
            least_need = need;
            least_remain = remain;
        } else if (need == least_need && remain < least_remain) {
            path = temp_path;
            least_remain = remain;
        }
        temp_path.pop_back();
        return;
    }
    for (auto item:pre[root]) {
        DFS(item);
    }
    temp_path.pop_back();
}

int main() {
    scanf("%d%d%d%d", &Capacity, &nn, &Target, &mm);
    Capacity /= 2;
    for (int i = 1; i <= nn; ++i) {
        scanf("%d", &ori_bikes[i]);
        ori_bikes[i] -= Capacity;
    }
    fill(graph[0], graph[0] + 501 * 501, INF);
    int v1, v2, weight;
    for (int i = 0; i < mm; ++i) {
        scanf("%d%d%d", &v1, &v2, &weight);
        graph[v1][v2] = graph[v2][v1] = min(weight, graph[v2][v1]);
    }
    Dijkstra(0);
    DFS(Target);
    printf("%d ", least_need);
    for (int i = path.size() - 1; i >= 0; --i) {
        printf("%d", path[i]);
        if (i > 0) printf("->");
    }
    printf(" %d\n", least_remain);
    return 0;
}