[Gold / 1753] 최단경로

문제 링크

---

🔷 분류

그래프 이론, 최단 경로, 데이크스트라

✒️ 문제 설명

방향그래프가 주어지면 주어진 시작점에서 다른 모든 정점으로의 최단 경로를 구하는 프로그램을 작성하시오. 단, 모든 간선의 가중치는 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를 출력하면 된다.

💻 코드 (C++)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

#define INF 0x3f3f3f3f
int v, e, k;

typedef pair<int, int> node;
vector<node> A[20001];
bool visited[20001];
int len[20001];
priority_queue<node, vector<node>, greater<node>> q;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> v >> e >> k;
	fill(len, len + 20001, INF);
	for(int i = 0; i < e; i++) {
		int u, v, w;
		cin >> u >> v >> w;
		A[u].push_back({v, w});
	}
	
	// Dijkstra
	q.push({0, k});
	len[k] = 0;
	
	while(!q.empty()) {
		auto now = q.top();
		q.pop();
		int now_n = now.second;
		if(visited[now_n]) continue; // 이미 방문 했으면 넘어가기
		visited[now_n] = true;
		
		for(int i = 0; i < A[now_n].size(); i++) { // 지금 노드랑 연결된 거 순회하면서
			auto next_n = A[now_n][i].first;  // 노드랑
			auto next_v = A[now_n][i].second; // 값 저장
			
			if(len[next_n] > len[now_n] + next_v) { // 최소 거리 업데이트
				len[next_n] = next_v + len[now_n];
				q.push({len[next_n], next_n});
			}
		}
	}
	for(int i = 1; i <= v; i++) { // 거리 출력
		if(visited[i]) {
			cout << len[i] << "\n";
		} else {
            cout << "INF" << "\n";
        }
	}
	return 0;		
}