[백준 1753] 최단경로(Java)

1. 문제

www.acmicpc.net/problem/1753

1753번: 최단경로

2. 풀이

• 다익스트라로 풀었다.
• visited를 사용하지 않았더니 시간초과가 나와 visited로 갔던 경로는 true로 처리하였다.

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {

	static class Edge implements Comparable<Edge>{
		int to, weight;

		public Edge(int to, int weight) {
			super();
			this.to = to;
			this.weight = weight;
		}

		@Override
		public int compareTo(Edge o) {
			// TODO Auto-generated method stub
			return weight-o.weight;
		}
		
	}
	
	static int n,m;
	static int[] dist;
	static boolean[]visited;
	static ArrayList<Edge>[]list;
	static final int INF = Integer.MAX_VALUE;
	static PriorityQueue<Edge> pq;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		int start = Integer.parseInt(br.readLine());
		
		dist = new int[n+1];
		visited = new boolean[n+1];
		list = new ArrayList[n+1];
		for(int i=1; i<=n; i++) {
            list[i] = new ArrayList<>();
        }
		Arrays.fill(dist, INF);
		
		for(int i =0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int weight = Integer.parseInt(st.nextToken());
			list[from].add(new Edge(to, weight));
		}
		dist[start]=0;
		
		dijkstra(start,0);
		
		for(int i =1; i<=n; i++) {
			if(dist[i]==INF) {
				System.out.println("INF");
			}else {
				System.out.println(dist[i]);
			}
		}
	}

	public static void dijkstra(int to, int weight) {
		pq= new PriorityQueue<>();
		pq.offer(new Edge(to, weight));
		while(!pq.isEmpty()) {
			Edge start = pq.poll();
			if(visited[start.to]) continue;
			visited[start.to]=true;
			for(Edge next : list[start.to]) {
				if(dist[next.to]>dist[start.to]+next.weight) {
					dist[next.to]=dist[start.to]+next.weight;
					pq.offer(new Edge(next.to, dist[next.to]));
				}
			}
		}
	}
}

반응형