PAT甲级1018. Public Bike Management
题意：
杭州市有公共自行车服务，为世界各地的游客提供了极大的便利。人们可以在任何一个车站租一辆自行车，并将其送回城市的任何其他车站。
公共自行车管理中心（PBMC）不断监测所有车站的实时能力。
如果一个车站正好半满，那么一个车站据说处于完美的状态。如果车站充满或空，PBMC将收集或发送自行车，以调整该车站的状况。此外，所有的车站也将进行调整。
当报告问题站时，
PBMC将始终选择到达该站的最短路径。如果有多于一条最短路径，则需要从PBMC发送的最少数量的自行车。
图1
图1说明了一个例子。站点由顶点表示，道路对应于边缘。
边缘上的数字是从另一个终端站到达一个终端站所需的时间。在顶点S内写入的数字是在S存储的自行车的当前数量。假设每个站的最大容量为10.为了解决S3处的问题，我们有两个不同的最短路径：
-
PBMC - > S1 - > S3。在这种情况下，必须从PBMC发送4辆自行车，
因为我们可以从S1收集1辆自行车，然后搭载5辆自行车到S3，这样两个车站都将处于完美的状态。 -
PBMC - > S2 - > S3。这条路径需要与路径1相同的时间，但是只有3条自行车从PBMC发送，因此是将被选择的自行车。
输入规格：
每个输入文件包含一个测试用例。对于每种情况，
第一行包含4个数字：Cmax（<= 100），始终是偶数，是每个站的最大容量; N（<= 500），车站总数; Sp，问题站的索引（站号从1到N编号，PBMC由顶点0表示）;和M，道路的数量。第二行包含N个非
负数Ci（i = 1，... N）其中每个Ci分别为Si处的当前自行车数。然后M行跟随，每个包含3个数字：Si，Sj和Tij，其描述了在站Si和Sj之间移动的时间Tij。一行中的所有数字都以空格分隔。
输出规格：
对于每个测试用例，
在一行中打印结果。首先输出PBMC必须发送的自行车数量。然后在一个空格之后，输出路径，格式如下：0-> S1 - > ...-> Sp。最后在另一个空间之后，输出我们必须在Sp的条件调整完美后我们必须收回PBMC的自行车数量。
请注意，如果这样的路径不是唯一的，
输出一个需要最少数量的自行车，我们必须收回到PBMC。法官的数据保证这样的道路是独一无二的。
思路：
- Dijkstra求出最短路径的长度。
- dfs求出所有最短路径的可能情况，放入vector
- 写一个vector的cmp函数排序，输出第一个元素就好了
注意点：
- back的自行车不能送回已经遍历过的点。比如2 10，就是send = 3， back = 5 而不是 send = 2， back = 2;
- 排序的地方。第7个测试点。相同路径长度排序应该是先比较send较小的情况，其次在比较back较小的情况。 很多别的博主都没提到。不然第7个测试点是不能过的。
ac代码：
C++
// pat1018.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<unordered_map>
using namespace std;
const int MAX = 0x7fffffff;
int map[505][505];
int station[505];
bool visit[505];
int dis[505];
vector<vector<int> > res;
int mcap;
void init(int n)
{
res.clear();
for (int i = 0; i <= n; i++)
{
station[i] = 0;
visit[i] = false;
dis[i] = i == 0 ? 0 : MAX;
for (int j = 0; j <= n; j++)
{
map[i][j] = i == j ? 0 : MAX;
}
}
}
void Dijkstra(int n)
{
int minst, minlong;
while (1)
{
minst = -1;
minlong = MAX;
for (int i = 0; i <= n; i++)
{
if (!visit[i] && dis[i] < minlong)
{
minlong = dis[i];
minst = i;
}
}
if (minst == -1) break;
visit[minst] = true;
for (int i = 1; i <= n; i++)
{
if (!visit[i] && map[i][minst] != MAX && minlong + map[i][minst] < dis[i])
dis[i] = minlong + map[i][minst];
}
}
}
void dfs(vector<int>& temp, int sum, int ending, int cur, int n)
{
if (sum > dis[ending]) return;
if (cur == ending && sum == dis[ending])
{
res.push_back(temp);
}
for (int i = 1; i <= n; i++)
{
if (!visit[i] && map[cur][i] != MAX)
{
visit[i] = true;
temp.push_back(i);
dfs(temp, sum + map[cur][i], ending, i, n);
visit[i] = false;
temp.pop_back();
}
}
}
void count(vector<int>& a,int& send,int& back)
{
send = back = 0;
int stanard = mcap / 2;
for (int i = 1; i < a.size(); i++)
{
if (station[a[i]] > stanard) back += station[a[i]] - stanard;
else if (station[a[i]] < stanard)
{
if (stanard - station[a[i]] - back >= 0)
{
send += stanard - station[a[i]] - back;
back = 0;
}
else
{
back -= stanard - station[a[i]];
}
}
}
}
static bool cmp(vector<int> a, vector<int> b)
{
int asend = 0, bsend = 0, aback = 0, bback = 0;
count(a, asend, aback);
count(b, bsend, bback);
//return asend + aback < bsend + bback;
if (asend != bsend) return asend < bsend;
else return aback < bback;
}
int main()
{
int nums, ending, mroads;
cin >> mcap >> nums >> ending >> mroads;
init(nums);
int temp;
for (int i = 1; i <= nums; i++)
{
cin >> station[i];
}
int s1, s2, t;
for (int i = 0; i < mroads; i++)
{
cin >> s1 >> s2 >> t;
map[s1][s2] = t;
map[s2][s1] = t;
if (s1 == 0) dis[s2] = t;
if (s2 == 0) dis[s1] = t;
}
Dijkstra(nums);
memset(visit, false, sizeof(visit));
vector<int> te(1,0);
dfs(te, 0, ending, 0, nums);
sort(res.begin(), res.end(), cmp);
int mysend = 0, myback = 0;
count(res[0], mysend, myback);
cout << mysend << " ";
for (int i = 0; i < res[0].size(); i++)
{
if (i == res[0].size() - 1) cout << res[0][i] << " ";
else cout << res[0][i] << "->";
}
cout << myback << endl;
return 0;
}