BOJ-1753_최단경로

[changicho]

1753. 최단경로

링크

난이도	정답률(_%)
Gold V	23 %

설계

다이크스트라 알고리즘

정리

내 코드	빠른 코드
112 ms

고생한 점

처음 간선을 입력받을 때, 중복되는 간선의 처리를 위해 연결을 순회하며 검사하는 코드를 작성했더니 시간초과가 발생했다.

코드

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <queue>

#define INF 987654321

using namespace std;

struct edge {
	int end, cost;
};

vector<vector<edge> > graph;
vector<int> costs;
int V, E;
int start; // start_point, K

void dijkstra() {
	// cost, start vertex
	// 기존 priority_queue는 내림차순으로 정렬한다.
	// 인접한 노드들을 방문할 때 비용이 최소인 노드부터 방문하므로 우선순위 큐에 비용을 음수 처리
	priority_queue< pair<int, int> > pq;
	pq.push({ 0, start });

	// 노드의 거리 갱신은 V-1 번 만큼 하면 된다. 
	while (!pq.empty()) {
		int now_node = pq.top().second;
		int cost = -pq.top().first;
		pq.pop();

		// 현재 노드에서 부터 주변에 있는 얘들의 값을 갱신한다. 
		for (edge current : graph[now_node]) {
			int new_val = costs[now_node] + current.cost;
			int before_val = costs[current.end];

			// 현재 노드로 부터 연결된 엣지의 목적지까지 가는 거리와 기존의 거리를 비교하여, 
			// 기존의 것이 더 크면 값을 갱신한다.  
			if (new_val < before_val) {
				int destination = current.end;

				costs[destination] = new_val;
				pq.push({ -new_val, destination });
			}
		}
	}
	return;
}

void solution() {
	cin >> V >> E;
	cin >> start;

	graph.resize(V + 1);
	costs.resize(V + 1);

	for (int i = 0; i < E; i++) {
		int from, to, cost;
		cin >> from >> to >> cost;

		graph[from].push_back(edge{ to,cost });
	}

	// initialize 
	for (int i = 1; i <= V; i++) {
		costs[i] = INF;
	}
	costs[start] = 0;

	// dijkstra
	dijkstra();

	for (int i = 1; i <= V; i++) {
		if (costs[i] == INF) {
			cout << "INF\n";
			continue;
		}
		cout << costs[i] << "\n";
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	solution();

	return 0;
}