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

2024-04-05 06:18

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

1018. Public Bike Management (30)

时间限制
400 ms
内存限制
32000 kB
代码长度限制
16000 B
判题程序
Standard
作者
CHEN, Yue

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.


Figure 1

Figure 1 illustrates an example. The stations are represented by vertices and the roads correspond to the edges. The number on an edge is the time taken to reach one end station from another. The number written inside a vertex S is the current number of bikes stored at S. Given that the maximum capacity of each station is 10. To solve the problem at S3, we have 2 different shortest paths:

1. PBMC -> S1 -> S3. In this case, 4 bikes must be sent from PBMC, because we can collect 1 bike from S1 and then take 5 bikes to S3, so that both stations will be in perfect conditions.

2. PBMC -> S2 -> S3. This path requires the same time as path 1, but only 3 bikes sent from PBMC and hence is the one that will be chosen.

Input Specification:

Each input file contains one test case. For each case, the first line contains 4 numbers: Cmax (<= 100), always an even number, is the maximum capacity of each station; N (<= 500), the total number of stations; Sp, the index of the problem station (the stations are numbered from 1 to N, and PBMC is represented by the vertex 0); and M, the number of roads. The second line contains N non-negative numbers Ci (i=1,...N) where each Ci is the current number of bikes at Si respectively. Then M lines follow, each contains 3 numbers: Si, Sj, and Tij which describe the time Tij taken to move betwen stations Si and Sj. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print your results in one line. First output the number of bikes that PBMC must send. Then after one space, output the path in the format: 0->S1->...->Sp. Finally after another space, output the number of bikes that we must take back to PBMC after the condition of Sp is adjusted to perfect.

Note that if such a path is not unique, output the one that requires minimum number of bikes that we must take back to PBMC. The judge's data guarantee that such a path is unique.

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
题意:

给一张图, 每个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 单源最短路径路径记录回溯的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/877832

相关文章

hdu2544(单源最短路径)

模板题: //题意:求1到n的最短路径,模板题#include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<queue>#include<set>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#i

poj 1502 MPI Maelstrom(单源最短路dijkstra)

题目真是长得头疼,好多生词,给跪。 没啥好说的,英语大水逼。 借助字典尝试翻译了一下,水逼直译求不喷 Description: BIT他们的超级计算机最近交货了。(定语秀了一堆词汇那就省略吧再见) Valentine McKee的研究顾问Jack Swigert,要她来测试一下这个系统。 Valentine告诉Swigert:“因为阿波罗是一个分布式共享内存的机器,所以它的内存访问

poj 1734 (floyd求最小环并打印路径)

题意: 求图中的一个最小环,并打印路径。 解析: ans 保存最小环长度。 一直wa,最后终于找到原因,inf开太大爆掉了。。。 虽然0x3f3f3f3f用memset好用,但是还是有局限性。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

hdu 3790 (单源最短路dijkstra)

题意: 每条边都有长度d 和花费p,给你起点s 终点t,要求输出起点到终点的最短距离及其花费,如果最短距离有多条路线,则输出花费最少的。 解析: 考察对dijkstra的理解。 代码: #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstrin

Node.js学习记录(二)

目录 一、express 1、初识express 2、安装express 3、创建并启动web服务器 4、监听 GET&POST 请求、响应内容给客户端 5、获取URL中携带的查询参数 6、获取URL中动态参数 7、静态资源托管 二、工具nodemon 三、express路由 1、express中路由 2、路由的匹配 3、路由模块化 4、路由模块添加前缀 四、中间件

记录每次更新到仓库 —— Git 学习笔记 10

记录每次更新到仓库 文章目录 文件的状态三个区域检查当前文件状态跟踪新文件取消跟踪(un-tracking)文件重新跟踪(re-tracking)文件暂存已修改文件忽略某些文件查看已暂存和未暂存的修改提交更新跳过暂存区删除文件移动文件参考资料 咱们接着很多天以前的 取得Git仓库 这篇文章继续说。 文件的状态 不管是通过哪种方法,现在我们已经有了一个仓库,并从这个仓

【408DS算法题】039进阶-判断图中路径是否存在

Index 题目分析实现总结 题目 对于给定的图G,设计函数实现判断G中是否含有从start结点到stop结点的路径。 分析实现 对于图的路径的存在性判断,有两种做法:(本文的实现均基于邻接矩阵存储方式的图) 1.图的BFS BFS的思路相对比较直观——从起始结点出发进行层次遍历,遍历过程中遇到结点i就表示存在路径start->i,故只需判断每个结点i是否就是stop

Android Environment 获取的路径问题

1. 以获取 /System 路径为例 /*** Return root of the "system" partition holding the core Android OS.* Always present and mounted read-only.*/public static @NonNull File getRootDirectory() {return DIR_ANDR

图的最短路径算法——《啊哈!算法》

图的实现方式 邻接矩阵法 int[][] map;// 图的邻接矩阵存储法map = new int[5][5];map[0] = new int[] {0, 1, 2, 3, 4};map[1] = new int[] {1, 0, 2, 6, 4};map[2] = new int[] {2, 999, 0, 3, 999};map[3] = new int[] {3, 7

学习记录:js算法(二十八):删除排序链表中的重复元素、删除排序链表中的重复元素II

文章目录 删除排序链表中的重复元素我的思路解法一:循环解法二:递归 网上思路 删除排序链表中的重复元素 II我的思路网上思路 总结 删除排序链表中的重复元素 给定一个已排序的链表的头 head , 删除所有重复的元素,使每个元素只出现一次 。返回 已排序的链表 。 图一 图二 示例 1:(图一)输入:head = [1,1,2]输出:[1,2]示例 2:(图