dijkstra+DFS模板题目
需要注意的是res和req的计算法则

#include<iostream>
#include<vector>
using namespace std;
const int INF = 1e9 + 10;
const int maxv = 510;
int G[maxv][maxv], d[maxv], current[maxv];
bool vis[maxv];
vector<int>path, temp;
int cmax, n, sp, m;
vector<int>pre[maxv];
void Dijkstra(int s)
{
    fill(d, d + maxv, INF);
    d[s] = 0;
    while (1)
    {
        int u = -1, MIN = INF;
        for (int i = 0; i <= n; i++)
        {
            if (!vis[i] && d[i] < MIN)MIN = d[i], u = i;
        }
        if (u == -1)return;
        vis[u] = true;
        for (int i = 0; i <= n; i++)
        {
            if (!vis[i] && G[u][i])
            {
                if (d[u] + G[u][i] < d[i])
                {
                    d[i] = d[u] + G[u][i];
                    pre[i].clear();
                    pre[i].push_back(u);
                }
                else if (d[u] + G[u][i] == d[i])
                {
                    pre[i].push_back(u);
                }
            }
        }
    }
}
int Minreq = INF, Minres = INF;
void DFS(int v)
{
    if (v == 0)
    {
        temp.push_back(0);
        int req = 0, res = 0;
        for (int i = temp.size()-2;i>=0;i--)
        {
            int v = temp[i];
            if (res + current[v] < cmax / 2)req += cmax / 2 - (res + current[v]), res = 0;
            else
            {
                if (current[v] > cmax / 2)
                {
                    res += current[v] - cmax / 2;
                }
                else
                {
                    res -= (cmax / 2 - current[v]);
                }
            }
        }
        if (req < Minreq)path = temp, Minreq = req, Minres = res;
        else if (req==Minreq&&res < Minres)path = temp, Minres = res;
        temp.pop_back();
        return;
    }
    temp.push_back(v);
    for (int i = 0; i < pre[v].size(); i++)DFS(pre[v][i]);
    temp.pop_back();
}
int main()
{
    scanf("%d%d%d%d", &cmax, &n, &sp, &m);
    for (int i = 1; i <= n; i++)scanf("%d", &current[i]);
    for (int i = 0; i < m; i++)
    {
        int a, b, t;
        scanf("%d%d%d", &a, &b, &t);
        G[a][b] = G[b][a] = t;
    }
    Dijkstra(0);
    DFS(sp);
    printf("%d ", Minreq);
    for (int i = path.size()-1;i>=0;i--)
    {
        printf("%d", path[i]);
        if (i != 0)printf("->");
    }
    printf(" %d", Minres);
    return 0;
}