[백준/C++] 1753. 최단경로

문제 

www.acmicpc.net/problem/1753

1753번: 최단경로

시작정점부터, 다른 모든 정점까지의 최단경로를 구하는 단순한(?) 문제이다. 

풀이

다익스트라 알고리즘을 이용하였다.

 

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

using namespace std;

#define INF 987654321

int min_route[20002];
int V, E, start;
vector<pair<int, int>> adj[20002];

void DijkstraHeap() {
	
	priority_queue<pair<int, int>> pq;
	pq.push(make_pair(0, start));
	min_route[start] = 0;

	while (!pq.empty()) {
		int dist = -pq.top().first;
		int cur = pq.top().second;
		pq.pop();
		if (min_route[cur] < dist) continue; // 이미 최단경로를 체크한 노드인 경우 패스 

		for (int i = 0;i < adj[cur].size();i++) {
			int there = adj[cur][i].first;
			int cost = dist + adj[cur][i].second;
			if (cost < min_route[there]) {
				min_route[there] = cost;
				pq.push(make_pair(-cost, there));
			}
		}
	}

}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> V >> E;
	cin >> start;
	for (int i = 0;i < E;i++) {
		int a, b, cost;
		cin >> a >> b >> cost;
		adj[a].push_back(make_pair(b, cost));
	}

	for (int i = 0;i <= V;i++) {
		min_route[i] = INF;
	}
	DijkstraHeap();
	
	for (int i = 1;i <= V;i++) {
		if (min_route[i] == INF)
			cout << "INF" << "\n";
		else
			cout << min_route[i] << "\n";
	}
	return 0;
}

 

결과

* endl -> "\n" 으로 변경했더니 800ms가 줄어들었다 

* 입출력시에 메인함수에 아래 코드를 넣지 않으면 시간초과가 난다

ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);