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