1018 Public Bike Management (30分)
这道题的难点在于如何求最少需要带来多少辆bike，需要最少带走多少辆bike。
注意： 在选定的最短路径各个节点中，每个节点必须都是perfect的。设PBMC为0号节点，如果第一个节点不是perfect，必须从PBMC中取，即带来。如果第一个节点bike数量充足，第二个节点不是perfect，可以用第一个节点中多余的bike来弥补第二个节点中bike的不足。以此类推。
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;const int inf = 0x3fffffff;
const int maxn = 505;//the total number of stations;int cmax, n, m, sp;
int bikeNum[maxn];
int Graph[maxn][maxn];
vector<int> pre[maxn];bool vis[maxn] = {
0};
int d[maxn];
vector<int >path, tempath;
int minNeed = inf, minRemain = inf;void Dijkstra(int s)
{
fill(d, d+maxn, inf);d[s] = 0;for(int i=0;i<n+1;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+1;v++){
if(!vis[v] && d[u] + Graph[u][v] < d[v]){
d[v] = Graph[u][v] + d[u];pre[v].clear();pre[v].push_back(u);}else if(!vis[v] && d[u] + Graph[u][v] == d[v]){
pre[v].push_back(u);}
// if(!vis[v] && Graph[u][v] != inf)
// {
// if(d[u] + Graph[u][v] < d[v])
// {
// d[v] = Graph[u][v] + d[u];
// pre[v].clear();
// pre[v].push_back(u);
// }
// if(d[u] + Graph[u][v] == d[v]){
// pre[v].push_back(u);
// }
// }}}
}void Dfs(int s)
{
if(s == 0){
tempath.push_back(s);int need = 0, remain = 0;int id;for(int i=tempath.size()-2;i>=0;i--){
//必须倒着遍历 id = bikeNum[tempath[i]];if(id - cmax / 2 > 0) //需要带走 remain += (id - cmax / 2);else if(id - cmax / 2 < 0) //需要弥补{
int temp = cmax / 2 - id;if(temp <= remain)remain -= temp;else{
need += (temp - remain);remain = 0;}}}if(need < minNeed)//需要弥补 {
minNeed = need;path = tempath; minRemain = remain;}else if(need == minNeed && remain < minRemain)//需要带走 {
minNeed = need;minRemain = remain;path = tempath; }tempath.pop_back();}tempath.push_back(s);for(int i=0;i<pre[s].size();i++)Dfs(pre[s][i]);tempath.pop_back();
} int main()
{
std::ios::sync_with_stdio(false);fill(Graph[0], Graph[0] + maxn*maxn, inf);cin>>cmax>>n>>sp>>m;for(int i=1;i<=n;i++)cin>>bikeNum[i];bikeNum[0] = 0;int a, b, time;for(int i=0;i<m;i++){
cin>>a>>b>>time;Graph[a][b] = Graph[b][a] = time;}Dijkstra(0);Dfs(sp);cout<<minNeed<<" ";for(int i=path.size() - 1;i>=0;i--){
cout<<path[i];if(i != 0)cout<<"->";}cout<<" ";cout<<minRemain<<endl;return 0;
}
在Dijkstra中，如果写成是：
for(int v=0;v<n+1;v++)
{
if(!vis[v] && Graph[u][v] != inf){
if(d[u] + Graph[u][v] < d[v]){
d[v] = Graph[u][v] + d[u];pre[v].clear();pre[v].push_back(u);}if(d[u] + Graph[u][v] == d[v]){
pre[v].push_back(u);}}
}
则会超时，如果改为：
for(int v=0;v<n+1;v++)
{
if(!vis[v] && d[u] + Graph[u][v] < d[v]){
//加不加!vis[v]也无所谓。d[v] = Graph[u][v] + d[u];pre[v].clear();pre[v].push_back(u);}else if(!vis[v] && d[u] + Graph[u][v] == d[v]){
pre[v].push_back(u);}}
}
就不会超时了。
注意：如果写第二种写法，const int inf = 0x3fffffff;不能是0x7fffffff。因为如果是0x7fffffff的话，0x7fffffff+0x7fffffff则会溢出。
还要注意的是：如果用的cin、cout的话，不关闭同步信号，也会超时。如果改为scanf、printf输入输出，则不会超时。
在这道题中，我也测试了一下，用cin、cout并且关闭同步信号，比scanf、printf作为输入输出还要快，可以自己测试一下。
也即：
很多人会说cin的速度比scanf慢很多, 其实不然.
cin慢的原因主要在于默认cin与stdin总是保持同步, 这一步是消耗时间大户.
只需要加上std::ios::sync_with_stdio(false)来关闭同步就好了, 速度甚至要优于scanf.
下面是使用cin、cout并且关闭同步的情况。
下面是使用scanf、printf的情况。
测试了很多次，基本上就是这样。
