【PAT1018】 Public Bike Management 单源最短路径路径记录回溯

本文主要是介绍【PAT1018】 Public Bike Management 单源最短路径路径记录回溯，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1018. Public Bike Management (30)

题意：

给一张图, 每个node都代表一个杭州的一个借或者还自行车站点, node上的值表示当前这个站点拥有多少量自行车, 每条边表示两个站点之间要花多少时间从一个站点到另一个站点, 给定一个有问题的站点, 求出从控制中心(PBMC)到该站点的最短路径并且使得带出去以及拿回来的自行车的数量最少.

分析：

①用最短路径算法(比如迪杰斯特拉)得到从PBMC到问题站点的所有最短路径；

②在Dijstra算法中，记录下每个节点的最优路径的上一节点，若有多个则全部记录下来；

③根据要求（带来最少带回最少），从目标节点的多个相同最短路径中找到最满足要求的一个；

④根据路径中记录的上一节点，进行回溯，直到根节点结束。

代码：

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <stack>
using namespace std;//此代码使用前，需删除下面两行+后面的system("PAUSE")
ifstream fin("in.txt");
#define cin fin
#define MAXNUM 501
int curNum[MAXNUM]={0};			//每个station的自行车数量
int link[MAXNUM][MAXNUM]={0};
int minSumPath[MAXNUM]={0};			//达到每个station的最短路径长度
bool visited[MAXNUM]={false};
const int INF = 0x7fffffff;struct LastNode{int lastid;		//上一个节点int bikeSum;	//到当下的车辆总数int staCount;	//到当下的站点总数LastNode(int l,int b,int s){lastid=l;bikeSum=b;staCount=s;}
};vector<LastNode>  vec[MAXNUM];int c,n,s,m;void push(int target,int dataid){			//把dataid节点的统计数据导入到target节点for(int i=0;i<vec[dataid].size();i++){vec[target].push_back(LastNode(dataid,vec[dataid][i].bikeSum+curNum[target],vec[dataid][i].staCount+1));}
}void Dij(int source,int target){int cen = source;vec[0].push_back(LastNode(-1,0,0));int min,minIndex,newSumPath;while(1){visited[cen]=true;min = INF;for(int i=1;i<=n;i++){if(visited[i])continue;if(link[cen][i]!=0){newSumPath = minSumPath[cen]+link[cen][i];if(minSumPath[i]==0 || minSumPath[i]>newSumPath){		//有更小路径，更新minSumPath[i] = newSumPath;vec[i].clear();				//先清空vector再导入push(i,cen);}else if(minSumPath[i] == newSumPath){		//路径相等，添加push(i,cen);				//再原有数据基础上添加}}if(min > minSumPath[i] && minSumPath[i]!=0){min = minSumPath[i];minIndex = i;}}if(minIndex == target){		//如果找到目标节点，直接跳出循环break;}cen = minIndex;		}
}stack<int> handleIndex(int index){		//根据目标节点回溯到0号节点，将路径存储在stack中stack<int> res;int id = index;int cen = s;int staCount,bikeSum;int i;while(1){staCount = vec[cen][id].staCount-1;bikeSum = vec[cen][id].bikeSum - curNum[cen]; res.push(cen);cen = vec[cen][id].lastid;if(cen == -1)break;			//回溯到根节点 则跳出循环for(i=0;i<vec[cen].size();i++){if(vec[cen][i].staCount == staCount && vec[cen][i].bikeSum == bikeSum){		//看上一个节点的哪条数据满足条件id = i;break;}}}return res;
}int main()
{cin>>c>>n>>s>>m;if(n==0 || s==0){cout<<"0 0 0"<<endl;return 0;}int i;for(i=0;i<n;i++)cin>>curNum[i+1];int a,b;for(i=0;i<m;i++){cin>>a>>b;cin>>link[a][b];link[b][a]=link[a][b];}Dij(0,s);int plusZero = INF;int plusIndex = -1;int minusZero = -1000000;int minusIndex = -1;int index = -1;int need;			//需要带来的车辆数vector<LastNode> tt = vec[s];for(i=0;i< tt.size();i++){			//在目标节点 所有相同的最短路径中 找带来最少 带回最少的路径下标need = tt[i].staCount*c/2 - tt[i].bikeSum;if(need > 0){if(need < plusZero){plusZero = need;plusIndex = i;}}else if(need < 0){if(need > minusZero){minusZero = need;minusIndex = i;}}else{index = i;}}stack<int> res;			int come,back;if(index != -1){res = handleIndex(index);		//根据目标节点回溯到0号节点come = 0;back = 0;}else if(plusIndex != -1){res = handleIndex(plusIndex);come = plusZero;back = 0;}else{res = handleIndex(minusIndex);come = 0;back = 0-minusZero;}cout<<come<<' ';cout<<res.top();		//输出路径res.pop();while(!res.empty()){cout<<"->"<<res.top();res.pop();}cout<<" "<<back<<endl;system( "PAUSE");return 0;
}

结果：

测试点	结果	用时(ms)	内存(kB)	得分/满分
0	答案正确	2	380	12/12
1	答案正确	2	372	2/2
2	答案正确	2	376	2/2
3	答案正确	2	376	2/2
4	答案正确	1	380	2/2
5	答案错误	2	256	0/2
6	答案正确	2	376	2/2
7	答案错误	2	376	0/3
8	答案正确	2	376	2/2
9	答案正确	5	1404	1/1

还有两个Case不过，没发现原因，就先放这里吧。

这篇关于【PAT1018】 Public Bike Management 单源最短路径路径记录回溯的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---