1753:최단경로

출발점 : K

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

int V, E;
int K;
const int MAX = 21e8;
static vector<int>result;
static vector<bool>visited;
struct Node {
	int to;
	int price;
};
static vector<vector<Node>>alist(20001);
bool operator<(Node left, Node right) {
	if (right.price < left.price)return 1;
	if (right.price > left.price)return 0;
	if (right.to > left.to)return 1;
	if (right.to < left.to)return 0;
	return 0;
}
static priority_queue<Node>q;

int main() {
	cin >> V >> E;
	cin >> K;
	for (int i = 0; i < E; i++) {
		int from, to, price;
		cin >> from >> to >> price;
		alist[from].push_back({ to,price });
	}
	visited.resize(V + 1);
	result.resize(V + 1);
	alist.resize(V + 1);
	std::fill(result.begin(), result.end(), MAX);
	std::fill(visited.begin(), visited.end(), false);
	result[K] = 0;
	q.push({ K,0 });
	while (!q.empty()) {
		Node now = q.top();
		q.pop();
		if (visited[now.to] == 1)continue;
		visited[now.to] = 1;
		for (int i = 0; i < alist[now.to].size(); i++) {
			Node next = alist[now.to][i];
			int total = now.price + next.price;
			if (result[next.to] > total) {
				result[next.to] = total;
				q.push({ next.to,total });
			}
		}
	}
	for (int i = 1; i <= V; i++) {
		if (visited[i])cout << result[i] << "\n";
		else cout << "INF" << "\n";
	}

	return 0;
}

[출력]

0
2
3
7
INF