[백] 1753 다익스트라 실습 1

메모리 초과가 계속 났다.
원인은 가중치를 받아두던 2차원 배열.
정점의 개수가 2만개라 2차원으로 배열을 만들면 1.6기가..? 하여간 대단한 메모리를 차지한다.
갈 수 있는 행선지를 받아두는 리스트에 가중치를 같이 받는 걸로 해결했다.

우선순위큐에다가 넣어서 제일 빨리 갈 수 있는 걸 먼저 다니게 한다 = 뒤에 더 돌 거를 미리 방지 = 시간 절약
더 빠른 길을 발견한 노드만 큐에 넣고 갱신한다 = 더 길면 돌아봤자 소용 없으니까
방문했었더라도 갱신할 거는 갱신해주는 걸 잊지 말도록 하자.
큐에서 꺼낼 때 방문처리를 하는 것도.

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

public class b1753 { 
	static int n;
	static int m;
	static int f;
	
	static int INF = Integer.MAX_VALUE;
	
    static boolean[] visit;
    static List<List<Node>> list = new ArrayList<>();
    
    static class Node implements Comparable<Node> {
    	int end, weight;
    	public Node(int end, int weight) {
    		this.end = end;
    		this.weight = weight;
    	}
    	
    	@Override
    	public int compareTo(Node o) {
    	// TODO Auto-generated method stub
    	return this.weight - o.weight;
    	}
    }

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		f = Integer.parseInt(st.nextToken());
		
		visit = new boolean[n+1];
		int[] dij = new int[n+1];
		for (int i = 0; i < n+1; i++) {
			list.add(new ArrayList<>());
			dij[i] = INF;
		}
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int de = Integer.parseInt(st.nextToken());
			int ar = Integer.parseInt(st.nextToken());
			int time = Integer.parseInt(st.nextToken());
			list.get(de).add(new Node(ar, time));
		}
		
		Queue<Node> que = new PriorityQueue<>();
		que.add(new Node(f, 0));
		dij[f] = 0;
		int vcnt = n;
		
		while (vcnt > 0 && !que.isEmpty()) {
			Node now = que.poll();
			if (visit[now.end]) continue;
			visit[now.end] = true;
			vcnt--;
			for (Node node : list.get(now.end)) {
				int i = node.end;
				int len = node.weight;
				if (dij[i] > now.weight + len) {
					if (!visit[i]) que.add(new Node(i, now.weight+len));
					dij[i] = now.weight + len;
				}
			}
		}
		
		for (int i = 1; i < dij.length; i++) {
			if (dij[i] == INF) bw.write("INF\n");
			else bw.write(dij[i] + "\n");
		}
        
        bw.flush();
        bw.close();
	}
}