250409 최단경로

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

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

	@Override
	public int compareTo(Edge o) {
		return this.weight - o.weight;
	}
}

public static void main(String[] args) throws IOException {
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	StringTokenizer st = new StringTokenizer(br.readLine());

	int vertexCount = Integer.parseInt(st.nextToken());
	int edgeCount = Integer.parseInt(st.nextToken());
	int start = Integer.parseInt(br.readLine());

	Edge[] graph = new Edge[vertexCount + 1];
	int[] dist = new int[vertexCount + 1];
	Arrays.fill(dist, Integer.MAX_VALUE);

	for (int i = 0; i < edgeCount; i++) {
		st = new StringTokenizer(br.readLine());
		int from = Integer.parseInt(st.nextToken());
		int to = Integer.parseInt(st.nextToken());
		int weight = Integer.parseInt(st.nextToken());

		graph[from] = new Edge(to, weight, graph[from]);
	}

	dijkstra(graph, dist, start);

	StringBuilder sb = new StringBuilder();
	for (int i = 1; i <= vertexCount; i++) {
		sb.append(dist[i] == Integer.MAX_VALUE ? "INF" : dist[i]).append("\n");
	}
	System.out.print(sb);
}

private static void dijkstra(Edge[] graph, int[] dist, int start) {
	PriorityQueue<Edge> pq = new PriorityQueue<>();
	dist[start] = 0;
	pq.add(new Edge(start, 0, null));

	while (!pq.isEmpty()) {
		Edge current = pq.poll();
		if (dist[current.to] < current.weight) {
			continue;
		}

		for (Edge next = graph[current.to]; next != null; next = next.next) {
			int newDist = current.weight + next.weight;
			if (dist[next.to] > newDist) {
				dist[next.to] = newDist;
				pq.add(new Edge(next.to, newDist, null));
			}
		}
	}
}

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