백준 1753 최단경로

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

using namespace std;

const int INF = 987654321;

struct Edge {
	int to;
	int cost;
	Edge(int _to, int _cost) :to(_to), cost(_cost){}
};

int N, M, a,b,c, start;
bool visited[20001];
int min_cost[20001];
vector<Edge> graph[20001];

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	cin >> start;
	for (int i = 0; i < M; i++)
	{
		cin >> a >> b >> c;
		graph[a].push_back(Edge(b, c));
	}
	for (int i = 1; i <= N; i++)
	{
		min_cost[i] = INF;
	}
	min_cost[start] = 0;
	priority_queue<pair<int, int>>pq;
	pq.push({ -min_cost[start],start });
	while (!pq.empty())
	{
		pair<int, int> cur = pq.top();
		pq.pop();
		int cur_vertex = cur.second;
		if (visited[cur_vertex])
		{
			continue;
		}
		visited[cur_vertex] = true;
		for (int i = 0; i < graph[cur_vertex].size(); i++)
		{
			Edge next = graph[cur_vertex][i];
			if (min_cost[next.to] > min_cost[cur_vertex] + next.cost)
			{
				min_cost[next.to] = min_cost[cur_vertex] + next.cost;
				pq.push({ -min_cost[next.to],next.to });
			}
		}
	}
	for (int i = 1; i <= N; i++)
	{
		if (min_cost[i] == INF)
		{
			cout << "INF\n";
		}
		else
		{
			cout << min_cost[i] << '\n';
		}
	}
	return 0;
}