(다익스트라) 백준 1753 - 최단경로

다익스트라 코드 요약

int visited[] = new int[V+1];
visited[start] = 1;

int dist[] = new int[V+1];
for(int k=0 ; k<V+1 ; k++) {
    dist[k] = Integer.MAX_VALUE;
}
dist[start] = 0;

PriorityQueue<Node> q = new PriorityQueue<Main.Node>();
q.add(new Node(start, 0));
        
while(!q.isEmpty()) {
	Node now = q.remove();
	for(int i=0 ; i<al[now.idx].size() ; i++ ) {
		Node next = al[now.idx].get(i);
			
		if(visited[next.idx] != 0)
			continue;
		if(dist[next.idx] > dist[now.idx] + next.cost)
			dist[next.idx] = dist[now.idx] + next.cost;
				
		q.add(new Node(next.idx, dist[next.idx]));
		visited[next.idx] = 1;
	}
}


static class Node implements Comparable<Node>{
	int idx, cost;
	Node(int idx, int cost){
		this.idx = idx;
		this.cost = cost;
	}
		
	@Override
	public int compareTo(Node o) {
		if(this.cost < o.cost) return -1;
		if(this.cost > o.cost) return 1;
		return 0;
	}
}

 

 

 

https://www.acmicpc.net/problem/1753

1753번: 최단경로

 

입력1

5 6
1
5 1 1
1 2 2
1 3 3
2 3 4
2 4 5
3 4 6

출력1

0
2
3
7
INF

 

---

코드

import java.io.*;
import java.util.*;

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer st;
	static class  Node implements Comparable<Node>{
		int idx;
		int cost;
		Node(int idx, int cost){
			this.idx  = idx;
			this.cost = cost;
		}
		
		@Override
		public int compareTo(Node o) {
			if(this.cost < o.cost) return -1;
			if(this.cost > o.cost) return 1;
			return 0;
		}
		
	}
	
	public static void main(String[] args) throws Exception {

		st = new StringTokenizer(br.readLine());
		int V = Integer.parseInt(st.nextToken());
		int E = Integer.parseInt(st.nextToken());
		
		int start = Integer.parseInt(br.readLine());
		
		ArrayList<Node>[] al = new ArrayList[V+1];
		for(int i=0 ; i<V+1 ; i++) {
			al[i] = new ArrayList<Main.Node>();
		}
		
		for(int j=0 ; j<E ; j++) {
			st = new StringTokenizer(br.readLine());
		    int s = Integer.parseInt(st.nextToken()); // start
		    int e = Integer.parseInt(st.nextToken()); // end
		    int c = Integer.parseInt(st.nextToken()); // cost
		    
		    al[s].add(new Node(e,c));
		}
		
		//다익스트라 시작
		int dist[] = new int[V+1];
		for(int k = 0 ; k<V+1 ; k++) {
			dist[k] = Integer.MAX_VALUE; // 무한대로 초기화
		}
		dist[start] = 0; // 자기자신은 0 만큼 갈 수 있음
		
		int visited[] = new int[V+1];
		visited[start] = 1;
        
		PriorityQueue<Node> q = new PriorityQueue<>();
		q.add(new Node(start, 0));
		
		
		while(!q.isEmpty()) {
			Node now = q.remove();
			for(int i = 0; i <al[now.idx].size() ; i++) {
				Node next = al[now.idx].get(i);
				if(visited[next.idx] != 0)
					continue;

				// 거리 확인후, 갱신
				if(dist[next.idx] > dist[now.idx] + next.cost) {
					dist[next.idx] = dist[now.idx] + next.cost;
				}
					
				// 큐 등록하고 방문처리
				q.add(new Node(next.idx, dist[next.idx]));
				visited[next.idx] = 1;
			}
		}

		for(int i=1 ; i <V+1 ; i++) {
			if(dist[i] == Integer.MAX_VALUE)
				System.out.println("INF");
			else System.out.println(dist[i]);
		}
		
		
	}
}