[C++] 백준 1753 : 최단 경로

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

1753번: 최단경로

백준 1753번 최단 경로를 풀어봤습니다.

우선순위 큐에서 두 번째 인자에 가중치를 넣었고 가중치를 오름차순으로 정렬하기 위해 compare 구조체를 정의했습니다. 인접리스트로 풀었고 큐에 시작점과 가중치 0을 넣고 다익스트라 함수에 넣었습니다. 그 후엔 다익스트라 함수에서 시작점과 인접한 정점부터 탐색을 시작합니다. BFS와 비슷한 구조인데 가중치만 추가된 것 같습니다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 2147483647

struct compare {
	bool operator()(pair<int, int>a, pair<int, int>b) {
		return a.second > b.second;
	}
};

vector<pair<int, int>> adjacent[20001];
priority_queue<pair<int, int>,vector<pair<int,int>>,compare> pq;
int v, e;

void dijkstra(vector<int> distance) {	
	while (!pq.empty()) {
		int current = pq.top().first;	// Current vertex
		int cost = pq.top().second;	// Cost of current vertex
		pq.pop();

		for (int i = 0; i < adjacent[current].size(); i++) {
			int next = adjacent[current][i].first;	// Next vertex
			int next_cost = adjacent[current][i].second + cost;	// Sum of cost
			if (next_cost < distance[next]) {
				distance[next] = next_cost;
				pq.push({ next,next_cost });
			}
		}
	}

	for (int i = 0; i < v; i++) {
		if (distance[i + 1] == INF)
			cout << "INF" << '\n';
		else
			cout << distance[i + 1] << '\n';
	}
}

int main() {
	cin >> v >> e;

	int start;
	cin >> start;

	for (int i = 1; i <= e; i++) {
		int from, to, weight;
		cin >> from >> to >> weight;
		adjacent[from].push_back({ to,weight });
		//adjacent[to].push_back({ from,weight });
	}
	

	vector<int> distance((v+1), INF);
	distance[start] = 0;

	pq.push({ start,distance[start]});
	dijkstra(distance);

	return 0;
}