这题也很好。涉及多条最短路径问题。使用Dijkstra找到多条最短路径，再使用DFS对路径进行回溯选取最佳的最短路径。
1.只用Dijkstra不能拿满分。
2.最短路径的优先级是（由高到低）：路径最短的；从PBMC取走的自行车数目最少的；从车站取回的自行车数目最少的。
3.存储多条最短路径的策略是，用二维数组vector<vector<int> >prev代替原来的一维数组存储前驱节点。思路是：
在Dijkstra算法中，专心求解前驱数组。
if(发现距离更短的路径){ 更新存放最短路径的数组; 清空这个点对应的前驱数组; 将这个点存入前驱数组 }else if(发现距离相同的路径){ 将这个点存入前驱数组 }
4.使用dfs遍历前驱数组。步骤是：
int bestValue; //存放第二标尺最优值（第一标尺是路径长短，第二标尺在本题中是从PBMC取走的自行车数目，第三标尺是从车站取回的自行车数目）
vector<int> pre[MAXN]; //前驱节点数组
vector<int> path; //存放最优路径
vector<int> tempPath; //存放临时路径
void DFS(int v){ //v为当前访问的节点
tempPath.push_back(v); //将v加入临时路径，进入dfs的节点都会被记录，tempPath存放着最短路径
//DFS的"死胡同"，递归边界
if(v == startPoint){ //遍历到了终点
int value; //在此计算第二标尺
if(value比bestValue更优){ //比较当前第二标尺与之前最优的第二标尺，确定是不是一条更优的路径
bestValue = value; //更新最优值
path = tempPath; //更新最优路径
}
}
//DFS的"岔路口"，递归式
else{ //v != startPoint，没遍历到终点
for(int i = 0; i < pre[v].size(); i++){//枚举容器内的所有前驱结点
DFS(pre[v][i]); //然后依次遍历
}
tempPath.pop_back(); //本节点找完了，删掉。以便遍历其他的
}
5.若在全局变量中定义prev，提交到pat会出现错误：“error: reference to 'prev' is ambiguous”，原因是和引用的库函数中定义的变量名重合了，解决方法是更改变量名，我就是把prev改成pre。
6.在全局变量中定义数组时，类似vector<int> data(N)（N是变量）的操作会出错，在全局变量中定义数组，数目一定要是常量。
7.如何更新需要带出的和需要带回的自行车数目，需要想清楚。思路可以是：
//send为需要从PBMC取出的总数目，back是需要带回到PBMC的总数目
从PBMC出发，终点是问题车站
如果车站的数目比“完美数目”多
则带走多的部分，加到back中记录；
如果比“完美数目”少，则比较back和当前车站缺少的数目
如果back>当前车站缺少的数目
表示从车站带出的自行车可以填补这一个车站的空缺，back剩余的数目是（back-当前车站缺少的数目），send值不变
如果back<=当前车站缺少的数目
表示从车站带出的自行车不能填补这一个车站的空缺，所有back填补到这一车站，该车站仍有（当前车站缺少的数目-back）的空缺，send加上这个空缺数目，就是需要从PBMC取出的总数目,back归0。
1 #include<iostream>
2 #include<cstdio>
3 #include<vector>
4 #include<algorithm>
5 #define inf 0x3f3f3f3f
6 using namespace std;
7 int C,N,SOS,M;
8 int minSend=inf,minBack=inf;
9 vector<int> dis(520,inf);
10 vector<vector<int> > pre(520);
11 vector<int> visited(520);
12 vector<int> bestPath,tempPath;
13 struct Edge{
14 int id;
15 int weight;
16 Edge(){
17 id=weight=0;
18 }
19 };
20 int k1,k2,weight;
21 Edge e;
22 vector<int> V(520);
23 vector<vector<Edge> > E(520);
24 void dfs(int v){
25 tempPath.push_back(v);//记录这个节点
26 if(v==0){//递归边界，终点 ,tempPath记录了其中一条最短路径
27 int send=0,back=0;
28 for(int i=tempPath.size()-1;i>=0;i--){
29 if(V[tempPath[i]]>0)
30 back+=V[tempPath[i]]; //累加需要带回的
31 else{
32 if(back>abs(V[tempPath[i]]))
33 back=back-abs(V[tempPath[i]]);//用需要带回的去补充缺少的
34 else{
35 send+=abs(V[tempPath[i]])-back;
36 back=0;
37 }
38 }
39 }
40 if(send<minSend){
41 bestPath=tempPath;
42 minSend=send;
43 minBack=back;
44 }
45 else if(send==minSend&&back<minBack){
46 minBack=back;
47 bestPath=tempPath;
48 }
49 }
50 else//如果不是终点 ，继续dfs
51 for(int i=0;i<pre[v].size();i++)//邻居
52 dfs(pre[v][i]) ;
53
54 tempPath.pop_back();//第一个运行至此的只能是终点，终点被访问完毕，弹出，末尾是终点之前的节点 x
55 // 此后程序退回到第26行，再次对终x进行dfs，如果x没有邻居，则又会运行至此，弹出x，路径又回退，以此类推
56 //即从终点一直回退，访问完所有可能的路径
57 }
58 int main(){
59 scanf("%d%d%d%d",&C,&N,&SOS,&M);
60 for(int i=1;i<=N;i++){
61 scanf("%d",&V[i]);
62 V[i]=V[i]-C/2;
63 }
64 for(int i=0;i<M;i++){
65 scanf("%d%d%d",&k1,&k2,&weight);
66 e.weight=weight;
67 e.id=k2;
68 E[k1].push_back(e);
69 e.id=k1;
70 E[k2].push_back(e);
71 }
72 dis[0]=0;
73 int min,m=0;
74 for(int i=0;i<N+1;i++){
75 min=inf;
76 for(int j=0;j<N+1;j++){
77 if(visited[j]==0&&min>dis[j]){
78 m=j;
79 min=dis[j];
80 }
81 }
82 visited[m]=1;
83 for(int j=0;j<E[m].size();j++){
84 int v=E[m][j].id;
85 if(visited[v]==0){
86 if(dis[m]+E[m][j].weight<dis[v])
87 { dis[v]=dis[m]+E[m][j].weight;
88 pre[v].clear();
89 pre[v].push_back(m);
90 }
91 else if(dis[m]+E[m][j].weight==dis[v])//是else if哦，保证上面的if如果执行了就不会执行这一段
92 pre[v].push_back(m);
93 }
94 }
95 }
96 dfs(SOS);
97 printf("%d 0", minSend);
98 for(int i = bestPath.size() - 2; i >= 0; i--)
99 printf("->%d", bestPath[i]);
100 printf(" %d", minBack);
101 return 0;
102 }
参考链接: