提交情况：
代码：
#include <iostream> #include <string.h> #include <vector> #include <math.h> using namespace std; #define Max 501 #define INF 0x3f3f3f3f int Cmax,n,sp,m; int visit[Max],dist[Max],weight[Max],w[Max]; int Graph[Max][Max]; vector<int> pre[Max],temp,path; int minNeed = INF,minRemain = INF; void Dijkstra ( int start ) //找到最短路径并存储最短路径 { visit[start] = 1; for( int i=0; i<=n; ++i) { int vertex = -1,min = INF; for( int j=0;j<=n;++j) //找到边权最小 { if( visit[j] == 0 && dist[j] < min ) { vertex = j; min = dist[j]; } } visit[vertex] = 1; for( int j=0;j<=n;++j) { if( visit[j] == 0 ) { if( dist[vertex] + Graph[vertex][j] < dist[j] ) //找到了更短的路径 { dist[j] = dist[vertex] + Graph[vertex][j]; //记录最短路径长度 pre[j].clear(); pre[j].push_back(vertex); //把最短路径上该节点的前驱节点记录下来 } else if( dist[vertex] + Graph[vertex][j] == dist[j] ) //最短路径相同 { pre[j].push_back(vertex); //如果有相同的最短路径，则把该前驱节点也记录下来 } } } } } void DFS( int start ) { if( start == 0) { temp.push_back(start); int need = 0,remain = 0; //need为当前车站需要补充的，remain为当前车站后剩余的 // cout<<"temp length:"<<temp.size()<<endl; for( int i = temp.size()-1;i>=0;--i) { // cout<<"节点为:"<<temp[i]<<endl; if( weight[temp[i]] > 0 ) //如果该车站有盈余，则将剩余的自行车数量加上该盈余 { remain = remain + weight[temp[i]]; } else //如果当前车站不足（weight[i]<=0） { if( remain > abs(weight[temp[i]]) ) //如果剩余的自行车数量大于所缺少的 { remain = remain - abs(weight[temp[i]]); } else //remain <= abs(weight[i]) { need += abs(weight[temp[i]]) - remain; remain = 0; } } } // cout<<need<<"***"<<remain<<endl; if( need < minNeed ) //需要从PBMC带的自行车数量更少 { minNeed = need; minRemain = remain; path = temp; } else if( need == minNeed && remain < minRemain ) //如果从PBMC带的自行车相同， { // 那么选择从问题车站带回最少的 minRemain = remain; path = temp; } temp.pop_back(); return ; } temp.push_back(start); for( int i=0;i<pre[start].size();++i ) { DFS(pre[start][i]); } temp.pop_back(); } int main () { cin>>Cmax>>n>>sp>>m; int pbmc = 0; for( int i=1;i<=n;++i ) { cin>>weight[i]; weight[i] = weight[i] - Cmax/2; memset(Graph[i],INF,sizeof(Graph[i])); } memset(Graph[0],INF,sizeof(Graph[0])); for( int i=1;i<=m;++i ) { int a,b; cin>>a>>b; cin>>Graph[a][b]; Graph[b][a] = Graph[a][b]; } //初始化 for( int i=0; i<=n; ++i) { if( Graph[pbmc][i] != INF ) { dist[i] = Graph[pbmc][i]; w[i] = weight[i]; pre[i].push_back(pbmc); } else dist[i] = INF; } Dijkstra(pbmc); // for( int i=0;i<=n;++i ) //查看最短路径上的前驱 // { // cout<<"第"<<i<<"节点的前驱："; // for( int j=0;j<pre[i].size();++j ) // { // if( j == pre[i].size()-1 ) // cout<<pre[i][j]<<endl; // else // cout<<pre[i][j]<<" "; // } // } // for( int i=0;i<=n;++i ) //查看weight数组 // { // if( i == n) // cout<<weight[i]<<endl; // else // cout<<weight[i]<<" "; // } // for( int i=0;i<=n;++i ) //查看dist数组 // { // if( i == n) // cout<<dist[i]<<endl; // else // cout<<dist[i]<<" "; // } DFS(sp); //从问题车站开始。该DFS算法并不是纯粹的深度优先算法。利用DFS遍历到达sp的最短路径 cout<<minNeed<<" "; for( int i = path.size()-1;i>=0;--i ) { if( i == 0 ) cout<<path[i]<<" "; else cout<<path[i]<<"->"; } cout<<minRemain<<endl; return 0; }这道题还是挺不错的，我不会做，看了算法笔记之后才明白的。 算法思想：利用Dijkstar求出最短路径，但是并不是只求最短的长度，还记录下最短路径上某一个节点的前驱节点，如果有相同的最短路径，那么同时也记录下来，放在某一个数组中。而后利用DFS算法，从问题车站开始，依次遍历到达问题车站的最短路径，在遍历过程统计需要的自行车和剩余的自行车。
