算法1

(Dijkstra + DFS)

blablabla

C++ 代码

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

#define MAXV 501
#define INF 0x3fffffff

int G[MAXV][MAXV];
int NeedBikes[MAXV];
int Dist[MAXV];
int Visited[MAXV];
int Nv, Ne, Cmax;
vector <int> PathList[MAXV], Path, recPath;

int minTSend = INF, minTBack = INF;

void DFS(int V, int End) {
    Path.push_back(V);
    if (V == End) { //最优解在求解过程中不满足最优子结构，需要得到最短路径后利用DFS进行遍历判定
        int Cnt = 0;
        int TakeIn = 0, TakeOut = 0;
        for (int i = Path.size() - 1; i >= 0; i--) { //0->后面开始
            int index = Path[i];
            if (NeedBikes[index] < 0) { //多出来了
                TakeOut += -NeedBikes[index];
            }
            else if (TakeOut > NeedBikes[index]) {
                TakeOut -= NeedBikes[index];
            }
            else {  
                TakeIn += NeedBikes[index] - TakeOut;
                TakeOut = 0;
            }
        }
        if (TakeIn < minTSend) {
            minTSend = TakeIn;
            minTBack = TakeOut;
            recPath = Path;
        }
        else if (TakeIn == minTSend && TakeOut < minTBack) {
            minTBack = TakeOut;
            recPath = Path;
        }
        Path.pop_back();
        return;
    }
    for (int W = 0; W < PathList[V].size(); W++) {
        DFS(PathList[V][W], End);
    }
    Path.pop_back();
}

void Dijkstra(int Start, int End) {
    fill(Dist, Dist + Nv, INF);
    fill(Visited, Visited + Nv, 0);
    Dist[Start] = 0;
    while (1) {
        int V = -1;
        int minD = INF;
        for (int i = 0; i < Nv; i++) {
            if (!Visited[i] && Dist[i] < minD) {
                minD = Dist[i];
                V = i;
            }
        }
        if (V == -1) break;
        Visited[V] = 1;
        for (int W = 0; W < Nv; W++) {
            if (!Visited[W] && G[V][W] != INF) {
                if (Dist[W] > Dist[V] + G[V][W]) {
                    Dist[W] = Dist[V] + G[V][W];
                    PathList[W].clear();
                    PathList[W].push_back(V);
                }
                else if (Dist[W] == Dist[V] + G[V][W]) {
                    PathList[W].push_back(V);
                }
            }
        }
    }
    DFS(End, Start);
    cout << minTSend << " ";
    int n = recPath.size() - 1;
    cout << recPath[n];
    for (int i = n - 1; i >= 0; i--) {
        cout << "->" << recPath[i];
    }
    cout << " " << minTBack;
}


int main() {
    int End, i;
    cin >> Cmax >> Nv >> End >> Ne; Nv++;
    fill(G[0], G[0] + MAXV * MAXV, INF);
    for (i = 1; i < Nv; i++) {
        int bikes;
        cin >> bikes;
        NeedBikes[i] = Cmax / 2 - bikes;
    }
    for (i = 0; i < Ne; i++) {
        int v, w;
        cin >> v >> w;
        cin >> G[v][w];
        G[w][v] = G[v][w];
    }
    Dijkstra(0, End);
}