摘要
Title: A1018 Public Bike Management
Tag: 最短路、DFS
Memory Limit: 64 MB
Time Limit: 1000 ms

A1018 Public Bike Management

题意

题意太复杂，简短版：
从起点PBMC出发，到需要维修的终点，路径中
- 路径长度最短
- 终点的车站调整最佳，途中的所有车站也会调整至最佳。
- 如果一个车站自行车存量刚满一半，则称其处于理想状态。
- 如果一个车站已满或空了，PBMC 会收集或派送自行车以将该车站的状况调整到最佳状态。
- 也就是三个优先级
  - 路径长度最短
  - 带去的车数量最少
  - 带回的车数量最少
求最短路、最短路径，最少带去车和最少带回车
思路

首先，需要一次dijkstra，求出最短路
然后，进行DFS所有最短路，途中记录三个值
- u, 代表目前到达哪个顶点
- s, 代表目前自行车的拿走和补贴情况
  - 如果s是正的，说明途中带回了自行车
  - 如果s是负的，说明途中需补充自行车
- mins, 代表s过程中的最小值，也就是我们需要路途中补满车站，所以最小值就是我们需要一开始从PBMC带的车
若DFS到了终点S，那么就是一条最短路径
- 每次DFS时，如果dist[u] + w == dist[v]，说明这条边是在最短路径上，可以走
- send，也就是我们一开始从起点拿多少车，就是mins（当然若mins大于0，说明不需要从起点拿车，send=0）
- bring，也就是我们最后带回多少车（一定是非负的），bring就等于 send + s，意思就是一开始我们补了多少车，再加上路途中车的变化量，就是最后剩下多少车
- 这样按优先级，规划出最优路径

代码

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-04 20:28:11
* @FilePath: \GPLT\A1018\A1018.cpp
* @LastEditTime: 2023-01-04 20:28:26
*/
#include <bits/stdc++.h>
#define SZ(X) ((int)(X).size())
using namespace std;

const int N = 510, INF = 0x3f3f3f3f;
typedef pair<int, int> PII;

int dist[N], st[N], c[N], bring = INF, send = INF, C, n, S, m;
vector<PII> g[N];
vector<int> path, ans;

void dij()
{
    memset(dist, 0x3f, sizeof dist);
    priority_queue<PII, vector<PII>, greater<PII>> q;
    q.push({0, 0});
    dist[0] = 0;
    while (SZ(q))
    {
        auto t = q.top();
        q.pop();
        auto u = t.second;
        if (st[u])
            continue;
        st[u] = 1;
        for (auto &[v, w] : g[u])
        {
            if (dist[u] + w < dist[v])
            {
                dist[v] = dist[u] + w;
                q.push({dist[v], v});
            }
        }
    }
    return;
}

int main()
{
    cin >> C >> n >> S >> m;
    for (int i = 1; i <= n; ++i)
        cin >> c[i];
    for (int i = 1; i <= m; ++i)
    {
        int x, y, z;
        cin >> x >> y >> z;
        g[x].push_back({y, z});
        g[y].push_back({x, z});
    }

    dij(); // 先做一遍dij

    path.push_back(0); // 路径加入起点

    function<void(int, int, int)> dfs = [&](int u, int s, int mins) {
        if (u)
        {
            s -= C / 2 - c[u]; // C保证是偶数
            mins = min(mins, s);
        }
        if (u == S)
        {
            int sd = abs(min(mins, 0));
            int br = sd + s;

            if (sd < send)
            {
                ans = path;
                send = sd;
                bring = br;
            }
            else if (sd == send && br < bring)
            {
                bring = br;
                ans = path;
            }
        }
        for (auto &[v, w] : g[u]) // 找u的邻边，dfs所有最短路
        {
            if (dist[u] + w == dist[v])
            {
                path.push_back(v);
                dfs(v, s, mins);
                path.pop_back();
            }
        }
    };

    dfs(0, 0, 0);

    cout << send << " ";
    cout << ans[0];
    for (int i = 1; i < SZ(ans); ++i)
        cout << "->" << ans[i];
    cout << " " << bring;
    return 0;
}

A1018 Public Bike Management

题意

思路

代码