[BAEKJOON] 1504번 : 특정한 최단 경로

문 제

 

소 스  코 드

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

constexpr int INF{ 0x7fff'0000 };

struct Edge {
	int nV;
	int mDis;

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

};

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

	void AddEdge(const int& a, const int b, const int c) {
		mGraph[a].emplace_back(Edge{ b, c });
		mGraph[b].emplace_back(Edge{ a, c });
	}

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

	void Dijkstra(const int& start) {
		if (start < 1 || start > mGraph.size()) return;

		while (!pQue.empty()) pQue.pop();

		for (int i = 1; i < mDist.size(); ++i) mDist[i] = INF;
		mDist[start] = 0;

		for (int i = 1; i < mDist.size(); ++i) pQue.push(Edge{ i, mDist[i] });
		
		while (!pQue.empty()) {
			Edge now{ pQue.top() };
			pQue.pop();

			if (mDist[now.nV] < now.mDis) continue;

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

	void GoThrough(const int& v1, const int& v2) {
		int p1[4]{ 0, };
		int p2[4]{ 0, };

		Dijkstra(1);
		p1[0] = mDist[v1];
		p2[0] = mDist[v2];

		Dijkstra(v1);
		p1[1] = mDist[v2];
		p2[1] = mDist[mGraph.size() - 1];

		Dijkstra(v2);
		p1[2] = mDist[mGraph.size() - 1];
		p2[2] = mDist[v1];
	
		
		for (int i = 0; i < 3; ++i) {
			if (p1[i] == INF) {
				p1[3] = -1;
				break;
			}
			else p1[3] += p1[i];
		}

		for (int i = 0; i < 3; ++i) {
			if (p2[i] == INF) {
				p2[3] = -1;
				break;
			}
			else p2[3] += p2[i];
		}

		std::cout << std::min(p1[3], p2[3]);
	}

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


};


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

	int N, E;
	std::cin >> N >> E;

	Graph graph(N);

	int a, b, c;
	for (int i = 0; i < E; ++i) {
		std::cin >> a >> b >> c;
		graph.AddEdge(a, b, c);
	}

	int v1, v2;
	std::cin >> v1 >> v2;
	graph.GoThrough(v1, v2);
	
	
	return 0;
}

 

풀 이

 

• [BAEKJOON] 1753번 : 최단경로

 

[ 백준 ] 1753번 : 최단경로에서 사용한 다익스트라 알고리즘을 통하여 길을 찾는 방법을 3번 사용하여 구현을 하였습니다.

 

먼저 v1, v2를 거쳐야하기 때문에

( 1 -> v1 ) + ( v1 -> v2 ) + ( v2 -> N )

( 1 -> v2 ) + ( v2 -> v1 ) + ( v1 -> N )

두 가지 경로의 거리를 확인해야 한다.

 

다익스트라 알고리즘의 경우.

dist배열에 시작지점에서 모든 점까지의 거리를 확인할 수 있기 때문에,

시작 지점이 1일 경우 : ( 1 -> v1 ) , ( 1 -> v2 ) 

시작 지점이 v1일 경우 : ( v1 -> v2 ) , ( v1 -> N )

시작 지점이 v2일 경우 : ( v2 -> v1 ) , ( v2 -> N )

 

다익스트라 알고리즘을 3번 1, v1, v2 를 확인하면 값을 구할 수 있다. 

 

 

출 력 값

 

 

문 제  출 처

문제 링크 : www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로