POJ 2449 제 k 최 단 경로

전형 적 인 문제 입 니 다. 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 입 니 다.

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

  다음 과 같이 AC 로 바 꿨 습 니 다.요즘 코드 를 자주 쓰 지 않 아서 그런 지 둔 해 졌 다.

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

 
  최종 AC 의 전체 코드:

import java.util.*;

class Node
{
	public Node()
	{
		lNodes = new ArrayList<LinkNode>();
	}
	public ArrayList<LinkNode> lNodes;
}

class LinkNode
{
	public LinkNode()
	{
		lid = 0;
		t = 0;
	}
	
	public LinkNode(int linkId, int time)
	{
		lid = linkId;
		t = time;
	}
	
	public int lid;
	public int t;
}

class HeapNode
{
	public HeapNode(int nid,int cv)
	{
		this.nodeId = nid;
		this.cvalue = cv;
	}
	
	public HeapNode()
	{
		
	}
	
	public HeapNode(int nid, int cv, int fv)
	{
		nodeId = nid;
		cvalue = cv;
		fvalue = fv;
	}
	
	public int nodeId;
	public int cvalue;
	public int fvalue;
}

class Comp1 implements Comparator<HeapNode>
{
	public int compare(HeapNode arg0, HeapNode arg1) {
		return arg0.cvalue - arg1.cvalue;
	}
}

class Comp2 implements Comparator<HeapNode>
{
	public int compare(HeapNode arg0, HeapNode arg1)
	{
		return (arg0.cvalue + arg0.fvalue) - (arg1.cvalue + arg1.fvalue); 
	}
}

public class Main {
	final static int MAX = 1<<30;
	
	public static int[] Dijkstra(ArrayList<Node> graph, int beg)
	{
		int n = graph.size();
		
		int funcArr[] = new int[n];
		boolean visFlag[] = new boolean[n];
		
		for(int i=0;i<n;i++)
		{
			funcArr[i] = MAX;
			visFlag[i] = false;
		}
		
		funcArr[beg-1] = 0;
	
		PriorityQueue<HeapNode> queue = new PriorityQueue<HeapNode>(graph.size(),new Comp1());
		queue.add(new HeapNode(beg, 0));
		
		
		while(queue.isEmpty() == false)
		{
			HeapNode tnode = queue.poll();
			if(visFlag[tnode.nodeId-1] == true)
				continue;
			visFlag[tnode.nodeId-1] = true;
			
			for(int i=0;i<graph.get(tnode.nodeId - 1).lNodes.size();i++)
			{
				LinkNode tlnode = graph.get(tnode.nodeId-1).lNodes.get(i);
				if(funcArr[tnode.nodeId - 1] + tlnode.t < funcArr[tlnode.lid-1])
				{
					funcArr[tlnode.lid-1] = funcArr[tnode.nodeId - 1]  + tlnode.t;
					queue.add(new HeapNode(tlnode.lid, funcArr[tlnode.lid-1]));
				}
			}
		}
		
		return funcArr;
		
	}
	
	public static int AStartKShortestPath(ArrayList<Node> graph, int beg, int end,int k,int[] funcArr)
	{
		if(beg==end)k++;
		int dis = -1;
		int kcount = 0;
		int n = graph.size();
		
		PriorityQueue<HeapNode> queue = new PriorityQueue<HeapNode>(n,new Comp2());
	
		queue.add( new HeapNode(beg,0,funcArr[beg-1]));
		
		while(queue.isEmpty() == false)
		{
			HeapNode hNode= queue.poll();
			if(hNode.nodeId == end)kcount++;
			if(kcount == k)
			{
				//System.out.println(hNode.nodeId+":"+hNode.cvalue+","+hNode.fvalue);
				dis = hNode.cvalue + hNode.fvalue;
				break;
			}
			for(int i=0;i<graph.get(hNode.nodeId-1).lNodes.size();i++)
			{
				LinkNode tlNode = graph.get(hNode.nodeId-1).lNodes.get(i);
				
				if(funcArr[tlNode.lid-1] < MAX)
				{
				  HeapNode tmphnode = new HeapNode(tlNode.lid, hNode.cvalue + tlNode.t, funcArr[tlNode.lid-1]);
				  queue.add(tmphnode);
				}
			}
		}
		
		
		return dis;
	}
	
	public static void main(String[] args)
	{	
		
		//Initialize the graph and transpose graph//////////////////////
		Scanner scan = new Scanner(System.in);
		int n,m;
		n = scan.nextInt();
		m = scan.nextInt();
		
		
		ArrayList<Node> graph = new ArrayList<Node>(n);
		ArrayList<Node> tgraph = new ArrayList<Node>(n);
		
		for(int i=0;i<n;i++)
		{
			graph.add(new Node());
			tgraph.add(new Node());
		}
		
		for(int i=0;i<m;i++)
		{
			int b,e,t;
			b = scan.nextInt();
			e = scan.nextInt();
			t = scan.nextInt();
			
			//Graph
			LinkNode tn0 = new LinkNode(e,t);
			graph.get(b-1).lNodes.add(tn0);
			
			//Transpose graph
			LinkNode tn1 = new LinkNode(b,t);
			tgraph.get(e-1).lNodes.add(tn1);
		}
		
		int s,t,k;
		s = scan.nextInt();
		t = scan.nextInt();
		k = scan.nextInt();
		/////////////////////////////////////////////
		
		int[] funcArr = Dijkstra(tgraph, t);
		int dis = AStartKShortestPath(graph, s, t, k, funcArr);
		
		
		System.out.println(dis);
		

	}

}