现在的位置: 首页 > 综合 > 正文

POJ3635 周游诸城:变形的SPFA/Dijkstra最短路+动规思想+Heap

2017年12月13日 ⁄ 综合 ⁄ 共 3455字 ⁄ 字号 评论关闭

  本来就有点小感冒,不过看到就快出国了,还是陪下爸妈,去海边玩了下,结果连续的长途开车奔波,加上海边游泳,消耗了不少体力,终于今天回来彻底病倒,喉咙痛到说不出话。打算这两天就把之前玩的一些题目给总结了吧,接下来得开始弄各种手续和那边导师安排的工作了。

  POJ3635,很有一道意思的题目,最后做出来后,你会发现它既有SPFA和Dijkstra的朴素思想,又有动态规划的巧妙,但是又不能生搬硬套这些算法

  我一开始想到的是用动规,推导出:

  costArr[i][j] = min{ ( e(i,i') + (j - k) ) * price[i']  + costArr[i‘][k] }

  其中costArr[i][j]为起点s到达某点i时,还剩下单位油量j的最小代价;e(i,i')表示相邻的两个点i,i'的边长;price[i]表示点i的单位汽油价格。该公式意思是枚举和点i相邻的各个状态:costArr[i'][k],从而找出最优的选择。

  得到该公式后,算法的流程就和Dijkstra几乎一样了,稍微不一样是这里把costArr[i'][k]当做一个状态。然后算法的每次迭代就从最小堆中拿出最小的costArr[i'][k],更新和它相邻的状态点costArr[i][j]。这样子一共有n*c个状态点。

  然后我根据该公式写成的代码,测试了好些数据,都ok,结果一提交,居然time exceeds limitation。无奈之下去再参考下别人的思路,发现该题时间要求比较严格,原来还要剪枝。如何剪枝?核心是“每个状态点,只加1单位油,或者不加油直接走到相邻状态点”,这样子也可以把所有的n*c个状态点给遍历。

  至于算法复杂度,窃以为,用最小堆实现,参考Dijkstra的算法复杂度分析,上面的原始算法和剪枝优化的复杂度都是为O( (nc+ec)*log(nc) ),只是剪枝优化后有点深度搜索的味道,尽可能的往纵深去搜索,实际应用中,往往只需要遍历更小的状态数就可以到达终点。这个分析,如有不对万望各位兄台指正。

 

import java.util.*;


class Node
{
	public Node()
	{
		nodeId = -1;
		price = 0;
		links = new ArrayList<Link>();
	}
	
	public Node(int id, int p)
	{
		nodeId = id;
		price = p;
		links = new ArrayList<Link>();
	}
	
	public int nodeId;
	public int price;
	public ArrayList<Link> links;
}

class Link
{
	public Link()
	{
		lnodeId = -1;
		distance = 0;
	}
	public Link(int nId, int dis)
	{
		lnodeId = nId;
		distance = dis;
	}
	
	public int lnodeId;
	public int distance;
}


class StateNode
{
	public StateNode()
	{
		
	}
	
	public StateNode(int nId, int cap, int cost)
	{
		this.nodeId = nId;
		this.cap = cap;
		this.cost = cost;
	}
	public int nodeId;
	public int cap;
	public int cost;
}

class Comp implements Comparator<StateNode>
{
	@Override
	public int compare(StateNode arg0, StateNode arg1) {
		return arg0.cost - arg1.cost;
	}
	
}

public class Main {
	
	public static int costArr[][] = new int[1001][101];
	public static boolean visFlag[][] = new boolean[1001][101];
	public static int MAX = 1<<30;
	
	
	//关键的算法函数。
	public static int DijSearch(ArrayList<Node>graph, int s, int e, int c)
	{
		int minCost = -1;
		int n = graph.size();
		
		for(int i=0;i<n;i++)
		{
			Arrays.fill(costArr[i], MAX);
			Arrays.fill(visFlag[i], false);
		}
		
		//Initialize the start node.
		costArr[s][0] = 0;
		
		PriorityQueue<StateNode> queue = new PriorityQueue<StateNode>(n*(c+1),new Comp());
		
		queue.add(new StateNode(s,0,0));
		
		while(queue.isEmpty() == false)
		{
			StateNode hn = queue.poll();
			
			if(hn.nodeId == e && hn.cap == 0)
			{
				minCost = hn.cost;
				break;
			}
			
			if(visFlag[hn.nodeId][hn.cap]  == true)
			{
				continue;
			}
			else
			{
				visFlag[hn.nodeId][hn.cap] = true;
			}
			
			//Plus one.
			if(hn.cap + 1 <= c && costArr[hn.nodeId][hn.cap+1] > costArr[hn.nodeId][hn.cap] + graph.get(hn.nodeId).price)
			{
				costArr[hn.nodeId][hn.cap+1] = costArr[hn.nodeId][hn.cap] + graph.get(hn.nodeId).price;
				queue.add(new StateNode(hn.nodeId,hn.cap+1,costArr[hn.nodeId][hn.cap+1]));
			}

			
			
			ArrayList<Link> links = graph.get(hn.nodeId).links;
			
			for(int i=0;i<links.size();i++)
			{
				int lnId = links.get(i).lnodeId;
				int linkDis = links.get(i).distance; 
				if(linkDis > c || linkDis > hn.cap)
					continue;
				

				// Go over costArr[ links[i].nodeId ][j]
				if ((visFlag[lnId][hn.cap - linkDis] == false)) {
					if ( (hn.cost < costArr[lnId][hn.cap - linkDis]) ) {
						costArr[lnId][hn.cap - linkDis] =  hn.cost;
						queue.add(new StateNode(lnId, hn.cap - linkDis, hn.cost));
					}
				}
				
				
			}
		}
		
		return minCost;
	}
	

	
	public static void main(String[] args)
	{
		Scanner scan = new Scanner(System.in);
		int n,m;
		n = scan.nextInt();
		m = scan.nextInt();
		
		//Initialize the graph
		ArrayList<Node> graph = new ArrayList<Node>(n);
		
		//The nodes
		for(int i=0;i<n;i++)
		{
			int pri = scan.nextInt();
			graph.add(new Node(i,pri));
		}
		
		//The edges
		for(int i=0;i<m;i++)
		{
			int u,v,d;
			u = scan.nextInt();
			v = scan.nextInt();
			d = scan.nextInt();
			
			
			graph.get(u).links.add(new Link(v,d));
			graph.get(v).links.add(new Link(u,d));
		}
		
		
		
		
		
		//The query
		int q,s,e,c;
		q = scan.nextInt();
		for(int i=0;i<q;i++)
		{
			c = scan.nextInt();
			s = scan.nextInt();
			e = scan.nextInt();
			
			int dis = DijSearch(graph, s, e, c); 
			
			if(dis == -1)
				System.out.println("impossible");
			else
				System.out.println(dis);
		}
	
	}

}


 

 

抱歉!评论已关闭.