1018 Public Bike Management

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.

The above figure 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:

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.
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 (≤), always an even number, is the maximum capacity of each station; N (≤), 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 (,) 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. 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:

Sample Output:

3 0->2->3 0

题意：

　　给出一张连通图，然后给出一个目标结点，求从结点0（PBMC）到目标结点的最短路。（这一部分用Dijkstra算法来求出最短路）

　　当然题目不会那么简单，在到达目标结点的过程中，途中经过的结点会存在一定数量的bike理想情况下每一个结点中存放的bike应该是最大容量的1/2，如果数量小于Cmax/2的话则需要往这里面运送车辆，如果之前结点中多出来的车辆不足以满足当前所需的车辆的话，则需要从PBMC中调遣车辆。

　　首先求出路径最短的路线，如果这样的路线有多个的话则选择从PBMC中调遣车辆最少的那条路线，如果仍然有多条路线可以选择，则选择最后调回PBMC车辆最少的那条路线。

　　如果当前结点的车辆需要补充，不能能够选择该节点之后剩余的车辆进行补充。

思路：

　　DFS + Dijkstra

Code：

 1 #include <bits/stdc++.h>
 2 
 3 using namespace std;
 4 
 5 const int inf = 0x7fffffff;
 6 
 7 vector<int> path, tempPath;
 8 vector<int> preVertex[505];
 9 vector<int> currentNumOfBikes(505);
10 int minNeed = inf, minBack = inf;
11 int Cmax, n, Sp, m;
12 
13 void DFS(int node) {
14     tempPath.push_back(node);
15     // 说明这时已经找到了一条路径
16     if (node == 0) {
17         int need = 0, back = 0;
18         for (int i = tempPath.size() - 2; i >= 0; --i) {
19             int id = tempPath[i];
20             if (currentNumOfBikes[id] + back < Cmax / 2) {
21                 need += Cmax / 2 - currentNumOfBikes[id] - back;
22                 back = 0;
23             } else {
24                 back += currentNumOfBikes[id] - Cmax / 2;
25             }
26         }
27         if (need < minNeed) {
28             minNeed = need;
29             minBack = back;
30             path = tempPath;
31         } else if (need == minNeed && back < minBack) {
32             minBack = back;
33             path = tempPath;
34         }
35         tempPath.pop_back();
36         return;
37     }
38     for (int it : preVertex[node]) DFS(it);
39     tempPath.pop_back();
40 }
41 
42 int main() {
43     cin >> Cmax >> n >> Sp >> m;
44     for (int i = 1; i <= n; ++i) cin >> currentNumOfBikes[i];
45     vector<vector<int> > grap(n + 1, vector<int>(n + 1, inf));
46     int v1, v2, t;
47     for (int i = 0; i < m; ++i) {
48         cin >> v1 >> v2 >> t;
49         grap[v1][v2] = grap[v2][v1] = t;
50     }
51     vector<bool> visited(n + 1, false);
52     vector<int> dis(n + 1, inf);
53     dis[0] = 0;
54     // Dijkstra寻找最短路
55     for (int i = 0; i <= n; ++i) {
56         int u = -1, minDis = inf;
57         for (int j = 0; j <= n; ++j) {
58             if (visited[j] == false && dis[j] < minDis) {
59                 u = j;
60                 minDis = dis[j];
61             }
62         }
63         // 当前的连通分量已经遍历完
64         if (u == -1) break;
65         visited[u] = true;
66         // 更新与当前最短路联通的下一个节点的距离
67         for (int j = 0; j <= n; ++j) {
68             if (visited[j] == false && grap[u][j] != inf) {
69                 if (minDis + grap[u][j] < dis[j]) {
70                     dis[j] = minDis + grap[u][j];
71                     preVertex[j].clear();
72                     preVertex[j].push_back(u);
73                 } else if (minDis + grap[u][j] == dis[j]) {
74                     preVertex[j].push_back(u);
75                 }
76             }
77         }
78     }
79 
80     DFS(Sp);
81     cout << minNeed << " 0";
82     for (int i = path.size() - 2; i >= 0; --i) cout << "->" << path[i];
83     cout << " " << minBack << endl;
84 
85     return 0;
86 }