個人學習記錄，代碼難免不盡人意。

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.


Sample Input:
10 3 3 5
6 7 0
0 1 1
0 2 1
0 3 3
1 3 1
2 3 1
Sample Output:
3 0->2->3 0

一開始我只用了dijkstra，結果只得到了23分。

#include <cstdio>
#include<set>
#include<string>
#include<algorithm>
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int cmax,n,sp,m;
const int maxn=510;
const int INF=1000000000;
int C[maxn];
int G[maxn][maxn];
int sent[maxn];
int take[maxn];
int d[maxn];
int pre[maxn];
bool visit[maxn]; 
void dijkstra(int st){fill(visit,visit+n+1,false);fill(d,d+n+1,INF);sent[st]=0;take[st]=0;d[st]=0;for(int i=0;i<=n;i++){int m=-1,min=INF;for(int j=0;j<=n;j++){if(!visit[j]&&d[j]<min){min=d[j];m=j;}}if(m==-1) return;visit[m]=true;for(int j=0;j<=n;j++){if(!visit[j]&&G[m][j]!=INF&&d[j]>d[m]+G[m][j]){d[j]=d[m]+G[m][j];
//				cout << "m=" << m <<"C[j]=" << C[j] <<endl; if(cmax/2-C[j]==0){sent[j]=sent[m];take[j]=sent[m];}else if(cmax/2-C[j]<0){//需要拿走 sent[j]=sent[m];take[j]=take[m]+abs(cmax/2-C[j]);}else{//需要帶來 sent[j]=max(0,(cmax/2-C[j])-take[m]);take[j]=max(0,take[m]-(cmax/2-C[j]));}pre[j]=m;}else if(!visit[j]&&G[m][j]!=INF&&d[j]==d[m]+G[m][j]){if(cmax/2-C[j]==0){if(sent[j]>sent[m]){sent[j]=sent[m];take[j]=take[m];pre[j]=m;}}else if(cmax/2-C[j]<0){//需要拿走 if(sent[j]>sent[m]){sent[j]=sent[m];take[j]=take[m]+abs(cmax/2-C[j]);pre[j]=m;}}else{//需要帶來 if(sent[j]>max(0,(cmax/2-C[j])-take[m])){sent[j]=max(0,(cmax/2-C[j])-take[m]);take[j]=max(0,take[m]-(cmax/2-C[j]));pre[j]=m;}}}}}
}
void dfs(int num){if(pre[num]==num){printf("%d",num);return;}dfs(pre[num]);printf("->%d",num);
}
int main(){scanf("%d%d%d%d",&cmax,&n,&sp,&m);C[0]=0;pre[0]=0;for(int i=1;i<=n;i++){scanf("%d",&C[i]);}for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){G[i][j]=INF;}}for(int i=1;i<=m;i++){int a,b,dis;scanf("%d%d%d",&a,&b,&dis);G[a][b]=dis;G[b][a]=dis;}dijkstra(0);
//  for(int i=0;i<n+1;i++){
//  	printf("%d ",take[i]);
//  }
//  for(int i=0;i<n+1;i++){
//  	printf("%d ",sent[i]);
//  }printf("%d ",sent[sp]);dfs(sp);printf(" %d\n",take[sp]);}

后來我看了答案才發現不能只使用dijkstra方法來做，因為路徑不滿足最優子結構，必須采用dijkstra和dfs的方法來做。
正確代碼如下：

//1018 Public Bike Management(30 分)
#include<cstdio>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
const int MAXV = 510;
const int INF = 1000000000;
int n, m, Cmax, Sp, numPath = 0, G[MAXV][MAXV], weight[MAXV];
int d[MAXV], minNeed = INF, minRemain = INF;//minNeed記錄最少攜帶的數目，minRemain記錄最少帶回的數目
bool vis[MAXV] = { false };
vector<int>pre[MAXV];
vector<int>tempPath, path;
void Dijkstra(int s) {fill(d, d + MAXV, INF);d[s] = 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) {if (d[u] + G[u][v] < d[v]) {d[v] = d[u] + G[u][v];pre[v].clear();pre[v].push_back(u);}else if (d[v] == d[u] + G[u][v])pre[v].push_back(u);}}}
}
void DFS(int v) {if (v == 0) {tempPath.push_back(v);//計算最短路徑標尺int need = 0, remain = 0;for (int i = tempPath.size() - 1; i >= 0; i--) {int id = tempPath[i];if (weight[id] > 0) {//如果當前節點點權為正，說明需要收走自行車，收走數量為點權值remain += weight[id];}else {//如果點權為負，則從前面收走的remain中向該節點投放自行車if (remain > abs(weight[id]))remain -= abs(weight[id]);else {//如果不夠投放，需要從PBMC攜帶need += abs(weight[id]) - remain;remain = 0;//當前持有的自行車全部用來補給}}}if (need < minNeed) {//最短路徑相同，選擇需要從PBMC帶的最少的情況minNeed = need;minRemain = remain;path = tempPath;}else if (need == minNeed && remain < minRemain) {//need還相同，選擇remain少的情況minRemain = remain;path = tempPath;}tempPath.pop_back();return;}tempPath.push_back(v);for (int i = 0; i < pre[v].size(); i++) {DFS(pre[v][i]);}tempPath.pop_back();
}
int main() {(void)scanf("%d %d %d %d", &Cmax, &n, &Sp, &m);int u, v;fill(G[0], G[0] + MAXV * MAXV, INF);for (int i = 1; i <= n; i++) {(void)scanf("%d", &weight[i]);weight[i] -= Cmax / 2;//點權減去容量的一半，計算距離prefect還差多少}for (int i = 0; i < m; i++) {(void)scanf("%d %d", &u, &v);(void)scanf("%d", &G[u][v]);G[v][u] = G[u][v];}Dijkstra(0);DFS(Sp);printf("%d ", minNeed);for (int i = path.size() - 1; i >= 0; i--) {//路徑的順序是倒序存放的printf("%d", path[i]);if (i > 0)printf("->");}printf(" %d", minRemain);return 0;
}