BOJ_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를 출력하면 된다.

---

# 코드

#include<iostream>
#include <vector>
#include<queue>

using namespace std;

class Node {
public:
	int vertex;
	int dist;
	Node(int vertex, int dist) : vertex(vertex), dist(dist) {};
	Node() {
		vertex = 0;
		dist = 0;
	}

	bool operator <(const Node& n) const {
		return dist > n.dist;
	}

	bool operator >(const Node& n) const {
		return dist < n.dist;
	}
};

int main() {
	ios::sync_with_stdio(false);
	int V, E, K, u, v, w, i, cost;
	cin >> V >> E >> K;
	int* visited = new int[V + 1]();
	for (i = 1; i < V + 1; i++) visited[i] = -1;
	vector< pair<int, int> >::iterator iter;
	vector< pair<int, int> > *edges = new vector< pair<int, int> >[V + 1];
	priority_queue<Node> pq;
	for (i = 0; i < E; i++) {
		cin >> u >> v >> w;
		edges[u].push_back(make_pair(v, w));
	}


	Node tmp;
	pq.push(Node(K, 0));
	visited[K] = 0;
	while (!pq.empty()) {
		tmp = pq.top();
		u = tmp.vertex;
		for (iter = edges[tmp.vertex].begin(); iter != edges[tmp.vertex].end(); iter++) {
			v = iter->first;
			w = iter->second;
			cost = tmp.dist + w;
			if (visited[v] == -1 || visited[v] > cost) {
				visited[v] = cost;
				pq.push(Node(v, cost));
			}
		}
		pq.pop();
	}

	for (i = 1; i < V + 1; i++) {
		if (visited[i] == -1) cout << "INF\n";
		else cout << visited[i] << "\n";
	}

	return 0;
}

처음에 시간초과 문제가 발생하여서, 질문란을 확인해보니 cin과 cout의 속도때문이라는 글이 있었다. Main함수에 ios::sync_with_stdio(false);를 추가하고, endl대신에 \n을 사용하였더니 해결되었다.

최대한 STL을 사용하는 방향으로 코드를 짜려고 했으나, C++에 익숙하지 않아 다음 링크에서 class로 priority_queue를 사용하는 방법을 참고하였다. https://hsp1116.tistory.com/42

아래 링크의 글에 priority_queue에 > 연산자는 오버로딩이 안될 것이다고 쓰여있어서 확인해보았다. > 연산자만 오버로딩하였을 때 이를 피연산자로 사용하는 연산자가 없다는 에러가 떴다. 또한 이 오버로딩을 지워도 코드가 정상 동작하였다. https://koosaga.com/9

---