PAT 1018. Public Bike Management
博客专区 > guoliang 的博客 > 博客详情
PAT 1018. Public Bike Management
guoliang 发表于4年前
PAT 1018. Public Bike Management
  • 发表于 4年前
  • 阅读 2143
  • 收藏 2
  • 点赞 1
  • 评论 4

腾讯云 技术升级10大核心产品年终让利>>>   

整体思路很简单,仅仅涉及到一个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;
}



共有 人打赏支持
粉丝 27
博文 115
码字总数 27457
评论 (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是不能求全的
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++就通过了。
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
指间沙

引用来自“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
能发一下代码吗?
×
guoliang
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: