[BAEKJOON] 1753번 : 최단경로

HiStar__ 2020. 9. 7. 21:20

문 제

소 스 코 드

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

constexpr int INF { 0x7fff'0000 };

struct Edge {
	int mV;
	int mWeight;	

	bool operator <(const Edge& other) const {
		return mWeight > other.mWeight;
	}

};

class Graph {
public:
	Graph() = delete;
	Graph(const int& v){ 
		mGraph.resize(v + 1);
		mDist.resize(v + 1);
	}

	void AddEdge(const int& u, const int v, const int w) {
		mGraph[u].emplace_back(Edge{ v, w });
	}

	void Display() {
		for (int i = 1; i < mGraph.size(); ++i) {
			std::cout << i << " : ";
			for (const auto& a : mGraph[i]) {
				std::cout << a.mV << " : " << a.mWeight << "  ";
			}
			std::cout << '\n';
		}
	}

	void SearchShortestPath(const int& start) {
		if (start < 0 || start > mDist.size()) return;

		for (int i = 1; i < mDist.size(); ++i) mDist[i] = INF;
		mDist[start] = 0;
		
		// Queue Clear
		while (!pQue.empty()) pQue.pop();

		for (int i = 1; i < mDist.size(); ++i) pQue.push(Edge{ i, mDist[i] });

		while (!pQue.empty()) {
			Edge temp{ pQue.top() };
			pQue.pop();

			if (mDist[temp.mV] < temp.mWeight) continue;

			for (const auto& a : mGraph[temp.mV]) {
				int plus{ mDist[temp.mV] + a.mWeight };
				if (mDist[a.mV] > plus) {
					mDist[a.mV] = plus;
					pQue.push(Edge{ a.mV, mDist[a.mV] });
				}
			}
		}

		for (int i = 1; i < mDist.size(); ++i) {
			if (INF == mDist[i]) std::cout << "INF \n";
			else				 std::cout << mDist[i] << '\n';
		}


	}


private:
	std::vector<std::vector<Edge>> mGraph; // weight, pos
	std::priority_queue<Edge> pQue;
	std::vector<int> mDist;

};

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	int V, E, K;

	std::cin >> V >> E >> K;

	Graph graph(V);

	int u, v, w;
	for (int i = 0; i < E; ++i) {
		std::cin >> u >> v >> w;
		graph.AddEdge(u, v, w);
	}

	graph.SearchShortestPath(K);


	return 0;
}

풀 이