POJ1724-ROADS

[POJ] [INDEX] [1724] [ROADS]

[Time: 1000MS] [Memory: 65536K] [难度: 中级] [分类: 搜索]

---

问题描述

给定一个图，图中每条路都有 路长Length 和 过路费Toll 两个参数，一条路连接两个城市，任意两个城市之间有且仅有一条路。

现在只有 K 块钱，要求从起点City1出发，到达终点CityN的最短路，也就是说在 K 花费内的最短路。

解题思路

这个题其实有很多种解法的，只不过是题目描述用的模型是最短路的模型，其实方法多种多样，Discuss里有同学用dijkstra+A*算法，也有人用BFS+优先队列，也有人用直接用STL的priotrity_queue+剪枝.....

我用了DFS+剪枝去做：

每个城市只能到达1次，每次找满足 Toll<RestMoney 的城市；当NowLen>MinLen就回溯，无需往下搜索了；递归出口是遍历所有允许的情况。

其实这题难度不大，关键是建立 邻接链表 去存储相同Source的路径去提高搜索效率。

因为Bob每进入一个Cityk，他就只能选择以k为源点的路径走向下一个城市，此时应该直接枚举所有以k为源点的路径。若使用了其他存储方式，则必然每次都要在所有路径中重新寻找以k为源点的路径，再枚举，这相当浪费时间。

测试数据

• 来源：CEOI 1998
• 下载：download
• 输入1：input-1
• 输出1：output-1
• 输入2：input-2
• 输出2：output-2
• 输入3：input-3
• 输出3：output-3

AC 源码

解题风格一： C++

//Memory Time 
//440K   250MS 

/*--- C++ Class ---*/

#include<iostream>
using namespace std;

class Road
{
	public:
		int S,D,L,T;  //Source,Destination,Length,Toll
		int next;     //指向相同Source的下一条边
};

class info
{
	public:
		info(int N,int R)
		{
			road=new Road[R+1];
			vist=new bool[N+1];
			ListTable_Head=new int[N+1];

			memset(vist,false,sizeof(bool)*(N+1));
			memset(ListTable_Head,-1,sizeof(int)*(N+1));
			MinLen=1e7;
			pr=0;
		}
		~info()
		{
			delete[] road;
			delete[] vist;
			delete[] ListTable_Head;
		}

		void input(int R);
		void output(void);
		void DFS(int NowCity,int NowLen,int RestMoney,int N);

	protected:
		Road* road;
		bool* vist;
		int* ListTable_Head;  //邻接链表头指针数组
		int MinLen;
		int pr;   //road[]指针
};

void info::input(int R)
{
	for(int i=1;i<=R;i++)
	{
		int s,d,l,t;
		cin>>s>>d>>l>>t;

		road[pr].S=s;
		road[pr].D=d;
		road[pr].L=l;
		road[pr].T=t;
		road[pr].next=ListTable_Head[s];
		ListTable_Head[s]=pr++;
	}
	return;
}

void info::output()
{
	cout<<(MinLen<1e7?MinLen:-1)<<endl;
	return;
}

void info::DFS(int NowCity,int NowLen,int RestMoney,int N)
{
	if(NowLen>MinLen)
		return;

	if(NowCity==N && RestMoney>=0 && NowLen<MinLen)
	{
		MinLen=NowLen;
		return;
	}

	for(int i=ListTable_Head[NowCity];i!=-1;i=road[i].next)
	{
		int tD=road[i].D;
		int tL=road[i].L;
		int tT=road[i].T;

		if(!vist[tD] && RestMoney>=tT)
		{
			vist[tD]=true;
			DFS(tD,NowLen+tL,RestMoney-tT,N);
			vist[tD]=false;
		}
	}
	return;
}

int main(void)
{
	int K,N,R;  //Money,CityNum,RoadNum
	while(cin>>K>>N>>R)
	{
		info poj1724(N,R);
		poj1724.input(R);
		poj1724.DFS(1,0,K,N);
		poj1724.output();
	}
	return 0;
}

解题风格二： C

//Memory Time 
//444K   235MS 

/*--- C Style ---*/

#include<iostream>
using namespace std;

const int inf=1e7;
const int CitySize=101;
const int RoadSize=10001;

struct
{
	int S,D,L,T;  //Source,Destination,Length,Toll
	int next;     //指向相同Source的下一条边
}road[RoadSize];

int pr;   //road[]指针
int K,N,R;  //Money,CityNum,RoadNum
int MinLen;
bool vist[CitySize];
int ListTable_Head[CitySize];  //邻接链表头指针数组

void DFS(int NowCity,int NowLen,int RestMoney)
{
	if(NowLen>MinLen)
		return;

	if(NowCity==N && RestMoney>=0 && NowLen<MinLen)
	{
		MinLen=NowLen;
		return;
	}

	for(int i=ListTable_Head[NowCity];i!=-1;i=road[i].next)
	{
		int tD=road[i].D;
		int tL=road[i].L;
		int tT=road[i].T;

		if(!vist[tD] && RestMoney>=tT)
		{
			vist[tD]=true;
			DFS(tD,NowLen+tL,RestMoney-tT);
			vist[tD]=false;
		}
	}
	return;
}

int main(void)
{
	while(cin>>K>>N>>R)
	{
		memset(ListTable_Head,-1,sizeof(ListTable_Head));
		memset(vist,false,sizeof(vist));
		pr=0;
		MinLen=inf;

		for(int i=1;i<=R;i++)
		{
			int s,d,l,t;
			cin>>s>>d>>l>>t;
			road[pr].S=s;
			road[pr].D=d;
			road[pr].L=l;
			road[pr].T=t;
			road[pr].next=ListTable_Head[s];
			ListTable_Head[s]=pr++;
		}

		DFS(1,0,K);

		cout<<(MinLen<inf?MinLen:-1)<<endl;
	}
	return 0;
}

---

版权声明

　　

• Site: http://exp-blog.com
• Mail: [email protected]

---