백준 1753

Q: 방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

INPUT: 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

처음엔 그냥 생각나는 대로 짰다.(지난 번에 사용했던 방법을 그대로 가져와서)

지난 번에는 vertex의 갯수가 1000개 정도여서 대충 풀어도 됐었는데, 이번엔 20,000개 정도라 그것으로는 너무 비효율적.

그래서 그래프에서 최단거리를 찾는 방법으로 풀었다.

그리고 시작하기 전에 두 vertices사이에 여러 edge가 있는 경우, 가장 짧은 것만 EdgeList에 넣고, 나머지는 버리는 방법, 

그리고 시작점으로 들어가는 Edge도 버리면 explore해야 할 edge의 수가 줄어들게 되어 조금 더 나을 것 같다.

아래는 EdgeList를 최적화하여 저장하는 방법은 적용하지 않은 코드

import java.util.*;

public class Main {
	class Edge implements Comparable<Edge>{
		int from;
		int to;
		int weight;
		public Edge(int from, int to, int weight) {
			this.from=from;
			this.to=to;
			this.weight=weight;
		}
		
		public String toString() {
			return "("+from+","+to+","+weight+")";
		}
		public boolean equals(Edge e) {
			if(this.from==e.from && this.to==e.to) {
				this.weight=(this.weight<e.weight)?this.weight:e.weight;
			}				
			return this.from==e.from && this.to==e.to;
		}
		public int compareTo(Edge e) {
			if(e.from<this.from) {
				return 1;
			}
			if(this.from<e.from) {
				return -1;
			}
			if(e.to<this.to) {
				return 1;
			}
			if(this.to<e.to) {
				return -1;
			}
			if(e.weight<this.weight) {
				return 1;
			}
			if(this.weight<e.weight) {
				return -1;
			}
			return 0;
		}
	}
	
	Edge[] edgeList;
	int numberOfVertices;
	int startPoint;
	Main(){}
	Main(Edge[] edgeList,int numberOfVertices, int startPoint){
		this.edgeList=edgeList;
		this.numberOfVertices=numberOfVertices;
		this.startPoint=startPoint;
	}
	
	
	public int[] getSortestPathFromStart() {
		int[] numberOfEdgesStartFrom0toN=new int[numberOfVertices+1];
		int numberOfEdges=edgeList.length;
		int i=0,j=0;
		for(;j<numberOfVertices && i<numberOfEdges;i++) {
			for(;edgeList[i].from>j+1;j++) {
				numberOfEdgesStartFrom0toN[j]=i;
			}
			if(edgeList[i].from==j+1) {
				numberOfEdgesStartFrom0toN[j++]=i;
			}
		}
		for(;j<=numberOfVertices;j++) {
			numberOfEdgesStartFrom0toN[j]=numberOfEdges;
		}
		int[] shortestPathFromStartToEachPoint=new int[numberOfVertices];

		HashSet<Integer> updated=new HashSet<Integer>(); // we store the POINT
		HashSet<Integer> updating=new HashSet<Integer>(); // we store the POINT
		updated.add(startPoint);
		for(;!updated.isEmpty();) {
			for(int a:updated) {
				for(i=numberOfEdgesStartFrom0toN[a-1];i<numberOfEdgesStartFrom0toN[a];i++) {
					if(edgeList[i].to!=startPoint) {
						if(shortestPathFromStartToEachPoint[edgeList[i].to-1]==0 
								|| shortestPathFromStartToEachPoint[edgeList[i].to-1]>shortestPathFromStartToEachPoint[a-1]+edgeList[i].weight) {
							shortestPathFromStartToEachPoint[edgeList[i].to-1]=shortestPathFromStartToEachPoint[a-1]+edgeList[i].weight;
							updating.add(edgeList[i].to);
						}
					}
				}
			}
			updated=updating;
			updating=new HashSet<Integer>();
		}
		return shortestPathFromStartToEachPoint;
	}
	
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		Main main=new Main();
		int numberOfVertices=sc.nextInt();
		int numberOfEdges=sc.nextInt();
		int startPoint=sc.nextInt();
		
		Edge[] edgeList=new Edge[numberOfEdges];
		for(int i=0;i<numberOfEdges;i++) {
			edgeList[i]=main.new Edge(sc.nextInt(),sc.nextInt(),sc.nextInt());
		}
		Arrays.sort(edgeList);
		main=new Main(edgeList,numberOfVertices,startPoint);
		int[] resultList=main.getSortestPathFromStart();
		for(int i=0;i<numberOfVertices;i++) {
			if(i==startPoint-1) {
				System.out.println(0);
			}
			else if(resultList[i]==0) {
				System.out.println("INF");
			}
			else {
				System.out.println(resultList[i]);
			}
			
		}
	}
}