1018 Public Bike Management
可以说是非常不在状态了。。。
这题是dijkstra求最短路，再dfs按照pre回溯。方括号小括号套的层数有点多，写蒙了。。。神奇的错误不断。。。
注意点是从0到nn的
冷静冷静再写一次吧233333先次饭饭🍚🍢嘻嘻

#include <cstdio>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;
const int INF = 0x3f3f3f3f;
int mmax, nn, target, mm;
vector<pair<int, int>> graph[510];
int station[510];
int dist[510], visited[510];
vector<int> pre[510];
int min_need = INF, min_back = INF;
vector<int> best_path, path; //node

void dijkstra(int src) {
    for (int i = 0; i <= nn; ++i) {
        visited[i] = false;
        dist[i] = INF;
    }
    dist[src] = 0;
    int min_dist, nearest;
    for (int j = 0; j <= nn; ++j) {
        min_dist = INF, nearest = INF;
        for (int k = 0; k <= nn; ++k) {
            if (!visited[k] && dist[k] < min_dist) {
                min_dist = dist[k];
                nearest = k;
            }
        }
        if (nearest == INF) break;
        visited[nearest] = true;
        for (int i = 0; i < graph[nearest].size(); ++i) {
            if (!visited[graph[nearest][i].first]) {
                int new_dist = dist[nearest] + graph[nearest][i].second;
                if (new_dist < dist[graph[nearest][i].first]) {
                    dist[graph[nearest][i].first] = new_dist;
                    pre[graph[nearest][i].first].clear();
                    pre[graph[nearest][i].first].push_back(nearest);
                } else if (new_dist == dist[graph[nearest][i].first]) {
                    pre[graph[nearest][i].first].push_back(nearest);
                }
            }
        }
    }
}

void dfs(int curr) {
    path.push_back(curr);
    if (curr == 0) {//PBMC
        int need = 0, back = 0;
        for (int i = path.size() - 1; i >= 0; --i) {
            int sta = path[i];
            int bias = 0 - station[sta];
            if (bias > 0) {
                if (back >= bias) {
                    back -= bias;
                } else {
                    need += bias - back;
                    back = 0;
                }
            } else {
                back += -bias;
            }
        }
        if (need < min_need) {
            min_need = need;
            min_back = back;
            best_path = path;
        } else if (need == min_need && back < min_back) {
            min_back = back;
            best_path = path;
        }
        path.pop_back();
        return;
    }
    for (int i = 0; i < pre[curr].size(); ++i) {
        dfs(pre[curr][i]);
    }
    path.pop_back();
}

int main() {
    scanf("%d%d%d%d", &mmax, &nn, &target, &mm);
    int perfect = mmax / 2;
    for (int i = 1; i <= nn; ++i) {
        scanf("%d", &station[i]);
        station[i] -= perfect;
    }
    int u, v, t;
    for (int j = 0; j < mm; ++j) {
        scanf("%d%d%d", &u, &v, &t);
        graph[u].push_back(make_pair(v, t));
        graph[v].push_back(make_pair(u, t));
    }
    station[0] = 0;
    dijkstra(0);
    dfs(target);
    printf("%d 0", min_need);
    for (int k = best_path.size() - 2; k >= 0; --k) {
        printf("->%d", best_path[k]);
    }
    printf(" %d\n", min_back);
    return 0;
}