好久没码 Dijkstra 了生疏了，还记得去年暑假在夏列营第一次听室友谈起这个名字的时候，觉得世界好神奇。那个时候有个人跟我说这名字怕不是滚键盘滚出来的哦，于是滚键盘就诞生了。 github 地址：https://github.com/iofu728/PAT-A-by-iofu728 难度：★★★★ 关键词：Dijkstra，DFS

# 题目

1018.Public Bike Management (30) There is a public bike service in Hangzhou City which provides great convenience to the tourists from all over the world. One may rent a bike at any station and return it to any other stations in the city.

The Public Bike Management Center (PBMC) keeps monitoring the real-time capacity of all the stations. A station is said to be in perfect condition if it is exactly half-full. If a station is full or empty, PBMC will collect or send bikes to adjust the condition of that station to perfect. And more, all the stations on the way will be adjusted as well.

When a problem station is reported, PBMC will always choose the shortest path to reach that station. If there are more than one shortest path, the one that requires the least number of bikes sent from PBMC will be chosen. Figure 1 illustrates an example. The stations are represented by vertices and the roads correspond to the edges. The number on an edge is the time taken to reach one end station from another. The number written inside a vertex S is the current number of bikes stored at S. Given that the maximum capacity of each station is 10. To solve the problem at S3, we have 2 different shortest paths:

1.PBMC -> S1 -> S3. In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from S1 and then take 5 bikes to S3, so that both stations will be in perfect conditions.

2.PBMC -> S2 -> S3. This path requires the same time as path 1, but only 3 bikes sent from PBMC and hence is the one that will be chosen.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 numbers: Cmax (<= 100), always an even number, is the maximum capacity of each station; N (<= 500), the total number of stations; Sp, the index of the problem station (the stations are numbered from 1 to N, and PBMC is represented by the vertex 0); and M, the number of roads. The second line contains N non-negative numbers Ci (i=1,…N) where each Ci is the current number of bikes at Si respectively. Then M lines follow, each contains 3 numbers: Si, Sj, and Tij which describe the time Tij taken to move betwen stations Si and Sj. All the numbers in a line are separated by a space. Output Specification: For each test case, print your results in one line. First output the number of bikes that PBMC must send. Then after one space, output the path in the format: 0->S1->…->Sp. Finally after another space, output the number of bikes that we must take back to PBMC after the condition of Sp is adjusted to perfect.

Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge’s data guarantee that such a path is unique.

Sample Input: 10 3 3 5 6 7 0 0 1 1 0 2 1 0 3 3 1 3 1 2 3 1 10 7 6 11 6 5 3 8 7 10 1 0 1 1 0 2 1 0 3 1 0 4 1 0 6 9 1 5 1 2 5 1 3 7 1 4 7 1 5 6 1 7 6 1

# 大意

选择距离最短的调度路线。在相同调度距离的路线总，选择调度量最小的路线。 PS：需要特别注意调度方向，可以看成有向图。

# 思路

1. 很显然这是一道 Dijkstra 的题目，而且不是裸 Dijkstra，是 Dijkstra 和 DFS 结合的题目。当时学 Dijkstra 的时候是用晴神宝典，记忆最深的就是这种题目。
2. Dijkstra 部分基本不需要改，直接套模板。遍历节点，找到目前能到的最近点，然后更新能到达的最短距离。（Dijkstra 的路径是用一种类似并查集的方法存放的，A[i]数组存放的是下一个节点，这对新手来说比较难理解。）
3. DFS 部分，就比较灵活。第一遍做的时候是取巧，当成无向图来做，遍历得到最短路径，计算最短的需要调度的算术值（就是简单的带正负号计算需要调度的值，没考虑方向），但是最后调出来，两个测试点没过（哇这题有个测试点）。 无奈只能老老实实重写 DFS，这遍写 DFS 的时候，考虑调度的方向，先把路径从并查集变成普通数组。在遍历路径，计算需要的车辆 out 和需要运送的车辆 in。具体两种不同的 DFS 会具体贴出来。

# code

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

const int maxn = 501;
const int INF = 0x3fffffff;
int G[maxn][maxn], unin[maxn], d[maxn];
bool vis[maxn];
int c, n, s, m, minout = INF, minin = INF;
vector<int> lines, linebest;
vector<int> store[maxn];
void Dijkstra() {
  fill(vis, vis + maxn, false);
  fill(d, d + maxn, INF);
  d[0] = 0;
  for (int i = 0; i <= n; ++i) {
    int u = -1, MIN = INF;
    for (int j = 0; j <= n; ++j) {
      if (vis[j] == false && d[j] < MIN) {
        u = j;
        MIN = d[j];
      }
    }
    if (u == -1) return;
    vis[u] = true;
    for (int v = 0; v <= n; ++v) {
      if (vis[v] == false && G[u][v] != INF && d[u] + G[u][v] <= d[v]) {
        if (d[u] + G[u][v] < d[v]) store[v].clear();
        store[v].push_back(u);
        d[v] = d[u] + G[u][v];
      }
    }
  }
}
void DFS(int st) {
  lines.push_back(st);
  if (st == 0) {
    int out = 0, in = 0;
    //      for(int i=0;i<lines.size();++i){
    //          cout<<lines[i]<<" ";
    //      }
    //      cout<<endl;
    for (int i = lines.size() - 2; i >= 0; --i) {
      int temp = lines[i], mid = c / 2;
      if (unin[temp] > mid) {
        in += (unin[temp] - mid);
        //              cout<<in<<" "<<out<<" 99"<<endl;
      } else {
        if (in + unin[temp] > mid) {
          in += (unin[temp] - mid);
          //                    cout<<in<<" "<<out<<" 98"<<endl;
        } else {
          out += (mid - (unin[temp] + in));
          in = 0;
          //                    cout<<in<<" "<<out<<" 97"<<endl;
        }
      }
    }
    if (out < minout) {
      minout = out;
      minin = in;
      linebest = lines;
    } else {
      if (out == minout && in < minin) {
        minin = in;
        linebest = lines;
      }
      lines.pop_back();
      return;
    }
  }
  for (int i = 0; i < store[st].size(); ++i) {
    DFS(store[st][i]);
  }
  lines.pop_back();
}
// void DFS(int st){
//  if(st==0){
//      int cost=spend-len*c/2;
//      if(abs(cost)<abs(spendmin)){
//          spendmin=cost;
//          linebest=lines;
//      }
//      return ;
//  }
//  vector<int> temp=store[st];
//
//  for(int i=0;i<temp.size();++i){
//      spend+=unin[temp[i]];
//      ++len;
//      lines.push_back(temp[i]);
//      DFS(temp[i]);
//      spend-=unin[temp[i]];
//      --len;
//      lines.pop_back();
//  }
//
//}
int main() {
  cin >> c >> n >> s >> m;
  fill(G[0], G[0] + maxn * maxn, INF);
  for (int i = 1; i <= n; ++i) {
    cin >> unin[i];
  }
  int line, row;
  for (int i = 0; i < m; ++i) {
    cin >> line >> row;
    scanf("%d", &G[line][row]);
    G[row][line] = G[line][row];
  }
  Dijkstra();
  //    for(int i=0;i<=n;++i){
  //        for(int j=0;j<store[i].size();++j){
  //            cout<<store[i][j]<<" ";
  //        }
  //        cout<<endl;
  //    }

  DFS(s);

  cout << minout << " ";
  for (int i = linebest.size() - 1; i > 0; --i) {
    cout << linebest[i] << "->";
  }
  cout << s << " " << minin << endl;
  return 0;
}