import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Scanner;
class Edge implements Comparable<Edge>{
public int vex; // 정점
public int cost; // 가중치 비용
Edge(int vex, int cost){
this.vex = vex;
this.cost = cost;
}
@Override
public int compareTo(Edge ob){
return this.cost - ob.cost; // 가중치 오름차순
// Edge 형의 priority queue를 만들면 작은 값 부터 우선순위
}
}
class Main{
static int n, m;
static int[] dis;
static ArrayList<ArrayList<Edge>> graph;
public void solution(int v){
PriorityQueue<Edge> pq = new PriorityQueue<>(); // cost가 가장 작은 것부터 꺼내짐
pq.offer(new Edge(v, 0));
dis[v] = 0;
while(!pq.isEmpty()){
Edge tmp = pq.poll(); // 가장 비용이 작은 엣지를 꺼냄
int now = tmp.vex;
int nowCost = tmp.cost;
if(nowCost > dis[now]) continue;
for(Edge ob: graph.get(now)){
if(dis[ob.vex] > nowCost + ob.cost){
dis[ob.vex] = nowCost + ob.cost; // 작은 비용으로 갱신
pq.offer(new Edge(ob.vex, nowCost+ob.cost));
}
}
}
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
n = sc.nextInt(); // 정점의 개수
m = sc.nextInt(); // 간선의 개수
graph = new ArrayList<ArrayList<Edge>>(); // Edge 객체를 저장할 수 있는 ArrayList
for(int i=0; i<=n; i++){
graph.add(new ArrayList<Edge>());
}
dis=new int[n+1];
Arrays.fill(dis, Integer.MAX_VALUE);
for(int i=0; i<m; i++){
int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
graph.get(a).add(new Edge(b,c)); // a번 정점에서 b번 정점으로 가는 비용 c
}
T.solution(1); // 1번 정점부터 시작
for(int i=2; i<=n; i++){
if(dis[i]!=Integer.MAX_VALUE) System.out.println(i+":"+dis[i]);
else System.out.println(i+":impossible");
}
}
}
'ALGORITHM' 카테고리의 다른 글
[JAVA] 알고리즘 : 그리디- 원더랜드 (크루스칼, 프림) (0) | 2022.11.25 |
---|---|
[JAVA] 알고리즘 : 그리디- 친구인가? (Disjoint-Set : Union&Find) (0) | 2022.11.25 |
[JAVA] 백준 13458- 시험 감독 (0) | 2022.11.25 |
[JAVA] 백준 1946- 신입 사원 (0) | 2022.11.24 |
[JAVA] 백준 11000- 강의실 배정 (0) | 2022.11.24 |