题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805489282433024

还是Dijkstra+DFS，重点是Dijkstra里的循环范围（因为不含起始点所以要+1）以及DFS函数的写法

代码

  1. #include<algorithm>
  2. #include<iostream>
  3. #include<cstdio>
  4. #include<vector>
  5. using namespace std;
  6. const int maxn = 510;
  7. const int inf = 0x3fffffff;
  8. int cmax, n, sp, m;
  9. int minNeed = inf, minRemain = inf;
  10. int weight[maxn], G[maxn][maxn], d[maxn];
  11. vector<int>pre[maxn];
  12. vector<int> path, tempPath;
  13. bool vis[maxn] = {false};
  15. void Dijkstra(int s){
  16.     fill(d, d + maxn, inf);
  17.     d[s] = 0;
  18.     for(int i = 0; i <= n; i++){
  19.         int u = -1, min = inf;
  20.         for(int j = 0; j <= n; j++){
  21.             if(vis[j] == false && d[j] < min){
  22.                 u = j;
  23.                 min = d[j];
  24.             }
  25.         }
  26.         if(u == -1) return;
  27.         vis[u] = true;
  28.         for(int v = 0; v <= n; v++){
  29.             if(vis[v] == false && G[u][v] != inf){
  30.                 if(G[u][v] + d[u] < d[v]){
  31.                     d[v] = G[u][v] + d[u];
  32.                     pre[v].clear();
  33.                     pre[v].push_back(u);
  34.                 } else if(G[u][v] + d[u] == d[v]){
  35.                     pre[v].push_back(u);
  36.                 }
  37.             }
  38.         }
  39.     }
  40. }
  42. void DFS(int v){
  43.     if(v == 0){//递归边界
  44.         tempPath.push_back(v);
  45.         int need = 0, remain = 0;
  46.         for(int i = tempPath.size() - 1; i >= 0; i--){
  47.             int id = tempPath[i];
  48.             if(weight[id] > 0){//多了
  49.                 remain += weight[id];
  50.             } else {//少了要补充
  51.                 if(remain > abs(weight[id])){//如果自己的够，那给光
  52.                     remain -= abs(weight[id]);
  53.                 } else {//如果不够，那就再need上面增加差的那一部分
  54.                     need += abs(weight[id]) - remain;
  55.                     remain = 0;//并把剩下的全给光
  56.                 }
  57.             }
  58.         }
  59.         if(need < minNeed){
  60.             minNeed = need;
  61.             minRemain = remain;
  62.             path = tempPath;
  63.         } else if(need == minNeed && remain < minRemain){
  64.             minRemain = remain;
  65.             path = tempPath;
  66.         }
  67.         tempPath.pop_back();
  68.         return;
  69.     }
  70.     tempPath.push_back(v);
  71.     for(int i = 0; i < pre[v].size(); i++){
  73.         DFS(pre[v][i]);
  74.     }
  75.     tempPath.pop_back();
  76. }
  78. int main(){
  79.     scanf("%d%d%d%d", &cmax, &n, &sp, &m);
  80.     fill(G[0], G[0] + maxn * maxn, inf);
  81.     for(int i = 1; i <= n; i++){
  82.         scanf("%d", &weight[i]);
  83.         weight[i] -= cmax / 2; 
  84.     }
  85.     int u, v;
  86.     for(int i = 0 ;i < m; i++){
  87.         scanf("%d%d", &u, &v);
  88.         scanf("%d", &G[u][v]);
  89.         G[v][u] = G[u][v];
  90.     }
  91.     Dijkstra(0);
  92.     DFS(sp);
  93.     printf("%d ", minNeed);
  94.     for(int i = path.size() - 1; i >= 0; i--){
  95.         printf("%d", path[i]);
  96.         if(i != 0) printf("->");
  97.     }
  98.     printf(" %d", minRemain);
  99.     return 0;
  100. }