[BOJ/백준] 1753 - 최단경로

1753번: 최단경로

---

다익스트라

---

---

• 제목

최단경로

---

• 조건

시간 제한 : 1 초

메모리 제한 : 256 MB 

---

• 문제

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 10 이하의 자연수이다.

---

• 입력

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두 정점 사이에 여러 개의 간선이 존재할 수도 있음에 유의한다.

---

• 출력

첫째 줄부터 V개의 줄에 걸쳐, i번째 줄에 i번 정점으로의 최단 경로의 경로값을 출력한다. 시작점 자신은 0으로 출력하고, 경로가 존재하지 않는 경우에는 INF를 출력하면 된다.

---

예제 입력1	예제 출력1
5 6 1 5 1 1 1 2 2 1 3 3 2 3 4 2 4 5 3 4 6	0 2 3 7 INF

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;
#define endl '\n'
#define INF 987654321
int dis[20001], sp;
vector<pair<int, int>> vt[20001];
void dijkstra(){
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq;
	dis[sp] = 0;
	pq.push(make_pair(dis[sp], sp));
	while(!pq.empty()){
		int cur_idx = pq.top().second;
		int cur_weight = pq.top().first;
		pq.pop();
		for(int n = 0; n < vt[cur_idx].size(); n++){
			int next_idx = vt[cur_idx][n].second;
			int next_weight = vt[cur_idx][n].first;
			// not min
			if(dis[next_idx] < cur_weight + next_weight) continue;
			dis[next_idx] = cur_weight + next_weight;
			pq.push(make_pair(dis[next_idx],next_idx));
		}
	}
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "r", stdin);

	int V, E, start, end, weight;

	cin >> V >> E >> sp;

	// default
	for(int n = 1 ; n <= V ; n++) dis[n] = INF;
	for(int n = 0 ; n < E ; n++){
		cin >> start >> end >> weight;
		vt[start].push_back(make_pair(weight, end));
	}
	dijkstra();
	for(int n = 1; n <= V; n++){
		if(dis[n] == INF) cout << "INF" << endl;
		else cout << dis[n] << endl;
	}
    return 0;
}