1753(다익스트라)

첫인상

가중치가 주어진 최단거리 탐색 즉 다익스트라 알고리즘을 이용해야 한다는 것을 알았다

풀이

우선순위큐를 사용하여 다익스트라 알고리즘을 구현하였다

문제 상황

런타임 에러(out of bounds)가 자꾸만 떴는 데 정점의 개수가 20000개라서 graph[20003]을 해주어야 하는데 실수로 graph[2003]을 해주고 다른 곳에서 문제를 정말 오랫동안 찾았다.

코드

#include<iostream>
#include<vector>
#include<queue>
#define pii pair<int,int>
using namespace std;

int v, e, start;
int INF = 98765432;
priority_queue<pii, vector<pii>, greater<pii>> pq;
vector<pii> graph[20003];
vector<int> ans;

void input() {
	cin >> v >> e >> start;

	int x, y, d;

	for (int i = 0; i < e; i++) {
		cin >> x >> y >> d;
		graph[x].push_back({ y,d });
	}

	for (int i = 0; i <= v; i++) {
		ans.push_back(INF);
	}
}

void solve() {
	pq.push({ 0,start });
	ans[start] = 0;

	while (!pq.empty()) {
		int cost = pq.top().first;
		int cur = pq.top().second;
		pq.pop();

		for (int i = 0; i < graph[cur].size(); i++) {
			int nxt = graph[cur][i].first;
			int ncost = graph[cur][i].second + cost;

			if (ans[nxt] > ncost) {
				ans[nxt] = ncost;
				pq.push({ ncost, nxt });
			}
		}
	}
}

int main() {
	input();
	solve();

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