[백준 1753] 최단경로(JAVA/C++)

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

1753번: 최단경로

 

 

 

[JAVA]

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

class Node{
	int v;
	int w;
	public Node(int v, int w) {
		super();
		this.v = v;
		this.w = w;
	}

}
public class Main {
	final static int INF=Integer.MAX_VALUE;
	static int V,E, start;
	static int[] distance;
	static List[] nodes;
	public static void main(String[] args) throws Exception{
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st= new StringTokenizer(br.readLine()," ");
		V=Integer.parseInt(st.nextToken());
		E=Integer.parseInt(st.nextToken());
		start=Integer.parseInt(br.readLine());
		nodes=new ArrayList[V+1];
		distance=new int[V+1];
		Arrays.fill(distance, INF);
		for(int i=1; i<=V; i++) {
			nodes[i]=new ArrayList();
		}
		for(int i=0; i<E; i++) {
			st= new StringTokenizer(br.readLine()," ");
			int u=Integer.parseInt(st.nextToken());
			int v=Integer.parseInt(st.nextToken());
			int w=Integer.parseInt(st.nextToken());
			nodes[u].add(new Node(v,w));
		}
		solve();
		for(int i=1; i<=V; i++) {
			if(distance[i]==INF) {
				System.out.println("INF");
			}else System.out.println(distance[i]);
		}
	}
	private static void solve() {
		PriorityQueue<Node> pq=new PriorityQueue<Node>(new Comparator<Node>() {
			@Override
			public int compare(Node o1, Node o2) {
				return o1.w-o2.w;
			}
		});
		distance[start]=0;
		pq.offer(new Node(start,0));
		while(!pq.isEmpty()) {
			Node n=pq.poll();
			for(int i=0; i<nodes[n.v].size(); i++) {
				Node next=(Node) nodes[n.v].get(i);
				int next_dist=n.w+next.w;
				if(next_dist<distance[next.v]) {
					distance[next.v]=next_dist;
					pq.offer(new Node(next.v,next_dist));
				}
			}
		}
		
	}

}

 

 

 

[C++]

#include <iostream> //다익스트라
#include <vector>
#include <queue>
#define SIZE 20001
#define INF 987654321

using namespace std;

int V, E, start;
int dist[SIZE];//1부터 시작
vector <pair<int, int> > vtx[SIZE];

void Solve() {
	priority_queue< pair<int, int>, vector<pair<int, int> >, greater<pair<int, int>> > pq;
	for (int i = 1; i <= V; i++) {
		dist[i] = INF;
	}
	dist[start] = 0;
	pq.push({ 0,start });
	while (!pq.empty()) {
		int cur_dist = pq.top().first;
		int cur_node = pq.top().second;
		pq.pop();
		//if (cur_dist > dist[cur_node]) continue;
		for (int i = 0; i < vtx[cur_node].size(); i++) {
			int next_dist = cur_dist+vtx[cur_node][i].second;
			int next_node = vtx[cur_node][i].first;
			if (next_dist < dist[next_node]) {
				pq.push({ next_dist ,next_node });
				dist[next_node] =next_dist;
			}
		}
	}
	for (int i = 1; i <= V; i++) {
		if (i == start) {
			cout << 0 << '\n';
		}
		else if (dist[i] == INF) {
			cout << "INF" << '\n';
		}
		else {
			cout << dist[i] << '\n';
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin >> V >> E >>start;
	int u, v, w;
	for (int i = 0; i < E; i++) {
		cin >> u >> v >> w;
		vtx[u].push_back({ v, w });
	}
	Solve();

	return 0;
}