文档章节

PAT 1018. Public Bike Management

guoliang
 guoliang
发布于 2013/09/14 23:24
字数 316
阅读 2317
收藏 2

整体思路很简单,仅仅涉及到一个dfs,得到0到某一点的路径,在从中记录下满足条件的路径。条件:距离最小,车携带数量最小,剩余自行车的数量最少。

C++代码

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <set>
#include <functional>
#include <string>
#include <queue>

using namespace std;

int Cmax,N,Sp,M;
int C[505];
int Road[505][505];
bool isReached[505];

int curLen = 0;
int minLen = 1<<30;
int curBike = 0;
int minBike = 1<<30;
int curSend = 0;
int minSend = 1<<30;
vector<int> curRoad;
vector<int> minRoad;

void dfs(int cur)
{
	if(curLen>minLen)
		return;
	if(cur == Sp)
	{
		bool choosed = false;
		if(curLen<minLen)
		{
			choosed = true;

		}else if(curLen == minLen)
		{
			if(curSend<minSend)
			{	
				choosed = true;
			}else if(curSend == minSend)
			{
				if(curBike<minBike)
				{
					choosed = true;
				}
			}
		}
		if(choosed)
		{
			minLen =  curLen;
			minSend = curSend;
			minBike = curBike;
			minRoad = curRoad;
		}
		return;
	}
	for(int i=0;i<=N;i++)
	{
		if(!isReached[i] && Road[cur][i]>0)
		{
			isReached[i] = true;
			curLen+= Road[cur][i];

			int lastCurSend = curSend;
			int lastCurBike = curBike;
			if(C[i]+curBike<Cmax/2){
				curSend += Cmax/2 - (C[i]+curBike);
				curBike = 0;
			}else{
				curBike = C[i]+curBike-Cmax/2;
			}
			curRoad.push_back(i);
			dfs(i);
			curRoad.pop_back();
			curSend = lastCurSend;
			curBike = lastCurBike;
			curLen-= Road[cur][i];
			isReached[i] = false;
		}
	}
}
int main()
{
	scanf("%d %d %d %d",&Cmax,&N,&Sp,&M);
	for(int i=1;i<=N;i++)
	{
		scanf("%d",C+i);
	}
	for(int i=0;i<M;i++)
	{
		int a,b,c;
		scanf("%d %d %d",&a,&b,&c);
		Road[a][b] = c;
		Road[b][a] = c;
	}
	isReached[0] = true;
	dfs(0);
	printf("%d ",minSend);
	printf("%d",0);
	for(int i=0;i<minRoad.size();i++)
	{
		printf("->%d",minRoad[i]);
	}
	printf(" %d",minBike);
	return 0;
}



© 著作权归作者所有

共有 人打赏支持
guoliang
粉丝 26
博文 131
码字总数 27457
作品 0
杭州
程序员
加载中

评论(4)

指间沙

引用来自“liwuqi”的评论

dijsktra求最小路径求不全面,比如0 1 1 0 2 1 1 3 1 2 3 1 3 4 1 3 5 1 4 6 1
5 6 1,那么0到6的最小路径,dijsktra是不能求全的

引用来自“heihei123”的评论

可以啊啊,骚年,不服来辩QQ:321727494
能发一下代码吗?
h
heihei123

引用来自“liwuqi”的评论

dijsktra求最小路径求不全面,比如0 1 1 0 2 1 1 3 1 2 3 1 3 4 1 3 5 1 4 6 1
5 6 1,那么0到6的最小路径,dijsktra是不能求全的
可以啊啊,骚年,不服来辩QQ:321727494
guoliang
guoliang

引用来自“liwuqi”的评论

dijsktra求最小路径求不全面,比如0 1 1 0 2 1 1 3 1 2 3 1 3 4 1 3 5 1 4 6 1
5 6 1,那么0到6的最小路径,dijsktra是不能求全的
我没有用dijstra算法,而是直接用的dfs回溯法,求路径的,现在改成c++就通过了。
liwuqi
liwuqi
dijsktra求最小路径求不全面,比如0 1 1 0 2 1 1 3 1 2 3 1 3 4 1 3 5 1 4 6 1
5 6 1,那么0到6的最小路径,dijsktra是不能求全的
使用 Play 框架开发的一些网站

Plan Cruncher Plan Cruncher creates a standard one-page summary of a business plan for a start-up company that is looking for external investment. You do this by choosing icons ......

红薯
2010/07/06
3.1K
5
30.3. cpu

[root@F5:Active] config # cat /proc/cpuinfo processor : 0 vendor_id : GenuineIntel cpu family : 6 model : 15 model name : Intel(R) Xeon(R) CPU X3220 @ 2.40GHz stepping : 11 cpu ......

玄学酱
01/08
0
0
如何查看服务器物理CPU数和CPU核数

原理比较简单,检查/proc/cpuinfo文件即可: 例如我的CPU # cat /proc/cpuinfo processor : 0 vendor_id : AuthenticAMD cpu family : 16 model : 5 model name : AMD Athlon(tm) II X4 6......

技术小胖子
2017/11/09
0
0
Java正则表达式问号冒号的使用

  在Java和Javascript中正则表达式字符串前面加上?:表示非捕获型匹配,否则就是捕获型匹配。   捕获型括号会将匹配到的内容捕获到一些变量里,这些变量按照捕获型括号的左括号为顺序从1...

浣雨笑笑生
2015/09/13
1K
0
java ascii码转换

@dbtop 你好,想跟你请教个问题:哥们这是你上次帮我解决的一个代码; static String regEx = "(10[1|0][1|0][1|0][1|0][1|0][1|0][1|0][1|0])"; public static void main(String[] args) {...

weng4570
2013/09/25
1K
2

没有更多内容

加载失败,请刷新页面

加载更多

下一页

@SpringBootApplication 注解

@SpringBootApplication注解是一个组合注解,包含以下注解 @Target(ElementType.TYPE) 注解的作用目标 @Retention(RetentionPolicy.RUNTIME) Reteniton的作用是定义被它所注解的注解保留多久,...

java.刘
38分钟前
0
0
sentinel自定义DataSource实战

序 本文主要研究一下如何自定义sentinel的DataSource,这里以jdbc为例。 maven <dependency><groupId>org.springframework.cloud</groupId><artifactId>spring-cloud-starter-sen......

go4it
53分钟前
1
0
xgboost/gbdt在调参时为什么树的深度很少就能达到很高的精度?

问题: 用xgboost/gbdt在在调参的时候把树的最大深度调成6就有很高的精度了。但是用DecisionTree/RandomForest的时候需要把树的深度调到15或更高。用RandomForest所需要的树的深度和Decisio...

tantexian
55分钟前
0
0
php-fpm的pool - 慢执行日志 - 进程管理 - open_basedir

php-fpm的pool : 为避免多站点使用同一个pool时因一个站点故障导致php资源耗尽,牵连使用同一个pool的其他站点的正常工作,可对每一个站点设置独立pool。 增加pool: 1.编辑php-fpm配置文件...

ZHENG-JY
今天
0
0
Linux之ssh服务默认端口修改

导读 SSH是标准的网络协议,可用于大多数UNIX操作系统,能够实现字符界面的远程登录管理,它默认使用22号端口,采用密文的形式在网络中传输数据,相对于通过明文传输的Telnet,具有更高的安全...

问题终结者
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部