백준 1504번 특정한 최단 경로 C++

출처 : https://www.acmicpc.net/problem/1504

 

다익스트라를 이용해서

(1~v1) + (v1~v2) + (v2~n) 과 (1~v2) + (v2~v1) + (v1~n) 중 경로가 작은 값을 출력했다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <limits.h>

using namespace std;
using int64 = long long;

int n, e;

vector<vector<int>> vertexs;

struct VertexCost {
	bool operator<(const VertexCost& other) const {
		return cost < other.cost;
	}
	bool operator>(const VertexCost& other) const {
		return cost > other.cost;
	}
	int vertex;
	int cost;
};

int Dijikstra(int start, int end) {
	vector<int> best(n + 1, INT_MAX);
	priority_queue<VertexCost, vector<VertexCost>, greater<VertexCost>> pq;
	pq.push({ start,0 });
	best[start] = 0;

	while (!pq.empty()) {
		auto curr = pq.top();
		pq.pop();

		if (curr.cost > best[curr.vertex])
			continue;

		for (int i = 1; i <= n; i++) {
			if (vertexs[curr.vertex][i] == -1)
				continue;
			int nextCost = curr.cost + vertexs[curr.vertex][i];
			if (nextCost >= best[i])
				continue;
			best[i] = nextCost;
			pq.push({ i,nextCost });
		}
	}
	return best[end];
}

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

	cin >> n >> e;
	vertexs = vector<vector<int>>(n + 1, vector<int>(n + 1, -1));
	for (int i = 0; i < e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		vertexs[a][b] = c;
		vertexs[b][a] = c;
	}
	int v1, v2;
	cin >> v1 >> v2;
	int startTov1 = Dijikstra(1, v1);
	int startTov2 = Dijikstra(1, v2);
	int v1Tov2 = Dijikstra(v1, v2);
	int v1Ton = Dijikstra(v1, n);
	int v2Ton = Dijikstra(v2, n);


	int dist1 = INT_MAX;
	int dist2 = INT_MAX;

	if (startTov1 != INT_MAX && v1Tov2 != INT_MAX && v2Ton != INT_MAX) {
		dist1 = startTov1 + v1Tov2 + v2Ton;
	}
	if (startTov2 != INT_MAX && v1Tov2 != INT_MAX && v1Ton != INT_MAX) {
		dist2 = startTov2 + v1Tov2 + v1Ton;
	}

	if (dist1 == INT_MAX && dist2 == INT_MAX) {
		cout << -1;
	}
	else {
		cout << min(dist1, dist2);
	}
};