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

POJ2449 第k最短路径 POJ2449 第k最短路径

2017年11月03日 ⁄ 综合 ⁄ 共 6062字 ⁄ 字号 小 中 大 ⁄ 评论关闭
 

POJ2449 第k最短路径

分类： Algorithm2013-07-06
17:04 149人阅读 评论(0) 收藏 举报
第k最短路POJ2449

  很经典的一道题目，第K最短路，很多应用都会用到的一个小算法。然后解法也很多，这里用了Dijkstra+A*搜索，每次从最小堆中弹出"c[x]+f[x]"值最小的结点x来继续访问，其中c[x]为从起点访问到x点的距离，f[x]为从x点到终点的最短距离。

  不过为了AC这道题目，倒是犯了几个小错误：

  1：根据题目，就算给定的起点s==给定的终点t，那么必须也要走，最短路径不能为0，所以就有了讨论中很多人说的那句代码 if(s==t)k++;

  2：这个错误我也搞不清楚状况，主要是用Dijkstra计算所有点到终点的最短路径时候，我一开始的代码如下，一直是wrong answer。

[java] view
plaincopy

  1. funcArr[beg-1] = 0;  
  2. visFlag[beg-1] = true;  
  3.   
  4. PriorityQueue<HeapNode> queue = new PriorityQueue<HeapNode>(graph.size(),new Comp1());  
  5. for(int i=0;i<graph.get(beg-1).lNodes.size();i++)  
  6. {  
  7.    LinkNode tlNode = graph.get(beg-1).lNodes.get(i);  
  8.    funcArr[tlNode.lid-1] = tlNode.t;  
  9.    queue.add(new HeapNode(tlNode.lid, funcArr[tlNode.lid-1]));  
  10. }  

  改为如下就AC了。难道是最近没有常写代码，都愚钝了。

[java] view
plaincopy

  1. funcArr[beg-1] = 0;  
  2.   
  3. PriorityQueue<HeapNode> queue = new PriorityQueue<HeapNode>(graph.size(),new Comp1());  
  4. queue.add(new HeapNode(beg, 0));  

 

  最终AC的完整代码：

[java] view
plaincopy

  1. import java.util.*;  
  2.   
  3. class Node  
  4. {  
  5.     public Node()  
  6.     {  
  7.         lNodes = new ArrayList<LinkNode>();  
  8.     }  
  9.     public ArrayList<LinkNode> lNodes;  
  10. }  
  11.   
  12. class LinkNode  
  13. {  
  14.     public LinkNode()  
  15.     {  
  16.         lid = 0;  
  17.         t = 0;  
  18.     }  
  19.       
  20.     public LinkNode(int linkId, int time)  
  21.     {  
  22.         lid = linkId;  
  23.         t = time;  
  24.     }  
  25.       
  26.     public int lid;  
  27.     public int t;  
  28. }  
  29.   
  30. class HeapNode  
  31. {  
  32.     public HeapNode(int nid,int cv)  
  33.     {  
  34.         this.nodeId = nid;  
  35.         this.cvalue = cv;  
  36.     }  
  37.       
  38.     public HeapNode()  
  39.     {  
  40.           
  41.     }  
  42.       
  43.     public HeapNode(int nid, int cv, int fv)  
  44.     {  
  45.         nodeId = nid;  
  46.         cvalue = cv;  
  47.         fvalue = fv;  
  48.     }  
  49.       
  50.     public int nodeId;  
  51.     public int cvalue;  
  52.     public int fvalue;  
  53. }  
  54.   
  55. class Comp1 implements Comparator<HeapNode>  
  56. {  
  57.     public int compare(HeapNode arg0, HeapNode arg1) {  
  58.         return arg0.cvalue - arg1.cvalue;  
  59.     }  
  60. }  
  61.   
  62. class Comp2 implements Comparator<HeapNode>  
  63. {  
  64.     public int compare(HeapNode arg0, HeapNode arg1)  
  65.     {  
  66.         return (arg0.cvalue + arg0.fvalue) - (arg1.cvalue + arg1.fvalue);   
  67.     }  
  68. }  
  69.   
  70. public class Main {  
  71.     final static int MAX = 1<<30;  
  72.       
  73.     public static int[] Dijkstra(ArrayList<Node> graph, int beg)  
  74.     {  
  75.         int n = graph.size();  
  76.           
  77.         int funcArr[] = new int[n];  
  78.         boolean visFlag[] = new boolean[n];  
  79.           
  80.         for(int i=0;i<n;i++)  
  81.         {  
  82.             funcArr[i] = MAX;  
  83.             visFlag[i] = false;  
  84.         }  
  85.           
  86.         funcArr[beg-1] = 0;  
  87.       
  88.         PriorityQueue<HeapNode> queue = new PriorityQueue<HeapNode>(graph.size(),new Comp1());  
  89.         queue.add(new HeapNode(beg, 0));  
  90.           
  91.           
  92.         while(queue.isEmpty() == false)  
  93.         {  
  94.             HeapNode tnode = queue.poll();  
  95.             if(visFlag[tnode.nodeId-1] == true)  
  96.                 continue;  
  97.             visFlag[tnode.nodeId-1] = true;  
  98.               
  99.             for(int i=0;i<graph.get(tnode.nodeId - 1).lNodes.size();i++)  
  100.             {  
  101.                 LinkNode tlnode = graph.get(tnode.nodeId-1).lNodes.get(i);  
  102.                 if(funcArr[tnode.nodeId - 1] + tlnode.t < funcArr[tlnode.lid-1])  
  103.                 {  
  104.                     funcArr[tlnode.lid-1] = funcArr[tnode.nodeId - 1]  + tlnode.t;  
  105.                     queue.add(new HeapNode(tlnode.lid, funcArr[tlnode.lid-1]));  
  106.                 }  
  107.             }  
  108.         }  
  109.           
  110.         return funcArr;  
  111.           
  112.     }  
  113.       
  114.     public static int AStartKShortestPath(ArrayList<Node> graph, int beg, int end,int k,int[] funcArr)  
  115.     {  
  116.         if(beg==end)k++;  
  117.         int dis = -1;  
  118.         int kcount = 0;  
  119.         int n = graph.size();  
  120.           
  121.         PriorityQueue<HeapNode> queue = new PriorityQueue<HeapNode>(n,new Comp2());  
  122.       
  123.         queue.add( new HeapNode(beg,0,funcArr[beg-1]));  
  124.           
  125.         while(queue.isEmpty() == false)  
  126.         {  
  127.             HeapNode hNode= queue.poll();  
  128.             if(hNode.nodeId == end)kcount++;  
  129.             if(kcount == k)  
  130.             {  
  131.                 //System.out.println(hNode.nodeId+":"+hNode.cvalue+","+hNode.fvalue);  
  132.                 dis = hNode.cvalue + hNode.fvalue;  
  133.                 break;  
  134.             }  
  135.             for(int i=0;i<graph.get(hNode.nodeId-1).lNodes.size();i++)  
  136.             {  
  137.                 LinkNode tlNode = graph.get(hNode.nodeId-1).lNodes.get(i);  
  138.                   
  139.                 if(funcArr[tlNode.lid-1] < MAX)  
  140.                 {  
  141.                   HeapNode tmphnode = new HeapNode(tlNode.lid, hNode.cvalue + tlNode.t, funcArr[tlNode.lid-1]);  
  142.                   queue.add(tmphnode);  
  143.                 }  
  144.             }  
  145.         }  
  146.           
  147.           
  148.         return dis;  
  149.     }  
  150.       
  151.     public static void main(String[] args)  
  152.     {     
  153.           
  154.         //Initialize the graph and transpose graph//////////////////////  
  155.         Scanner scan = new Scanner(System.in);  
  156.         int n,m;  
  157.         n = scan.nextInt();  
  158.         m = scan.nextInt();  
  159.           
  160.           
  161.         ArrayList<Node> graph = new ArrayList<Node>(n);  
  162.         ArrayList<Node> tgraph = new ArrayList<Node>(n);  
  163.           
  164.         for(int i=0;i<n;i++)  
  165.         {  
  166.             graph.add(new Node());  
  167.             tgraph.add(new Node());  
  168.         }  
  169.           
  170.         for(int i=0;i<m;i++)  
  171.         {  
  172.             int b,e,t;  
  173.             b = scan.nextInt();  
  174.             e = scan.nextInt();  
  175.             t = scan.nextInt();  
  176.               
  177.             //Graph  
  178.             LinkNode tn0 = new LinkNode(e,t);  
  179.             graph.get(b-1).lNodes.add(tn0);  
  180.               
  181.             //Transpose graph  
  182.             LinkNode tn1 = new LinkNode(b,t);  
  183.             tgraph.get(e-1).lNodes.add(tn1);  
  184.         }  
  185.           
  186.         int s,t,k;  
  187.         s = scan.nextInt();  
  188.         t = scan.nextInt();  
  189.         k = scan.nextInt();  
  190.         /////////////////////////////////////////////  
  191.           
  192.         int[] funcArr = Dijkstra(tgraph, t);  
  193.         int dis = AStartKShortestPath(graph, s, t, k, funcArr);  
  194.           
  195.           
  196.         System.out.println(dis);  
  197.           
  198.   
  199.     }  
  200.   
  201. } 
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞