백준 1504 특정한 최단 경로

특정한 최단 경로

---

문제

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1) 임의의 두 정점 u와 v사이에는 간선이 최대 1개 존재한다.

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

---

 

 

다익스트라를 이용하여 풀이하였다. 

특이하게 두 정점을 꼭 지나야 한다는 조건이 있어 어떻게 풀어야하나 당황스럽긴 하였는데,,, 구간을 나눠 거리를 측정해주면 나름 쉽게 풀 수 있는 문제였던 것 같다. 

 

다익스트라로 시작점부터 모든 정점까지 최단 거리를 구하는데, 가능한 경로가

root 1 = 1 -> v1 ->  v2 -> n

root 2 = 1 -> v2 -> v1 -> n 이렇게 두 가지 이므로 1, v1, v2를 시작점으로 해 총 3번의 다익스트라로 거리를 구하였다.

 

최악의 경우 800개의 정점에서 모두 거리가 1000일 때로 800,000이상의 거리값을 가질 경우 -1을 출력하고, 값이 너무 커 오버플로우가 일어났을 때도 -1을 출력하였다!!

 

#include<iostream>
#include<vector>
#include<set>
using namespace std;
using pii = pair<int, int>;
int n, e;

vector<vector<pii>>adj;
int d[801];

void dijkstra(int s) {
	for (int i = 1; i <= n; i++) {
		d[i] = 1 << 30;// 큰 값을 할당
	}
	set<pii>pq;
	pq.insert({ d[s] = 0,s });
	while (pq.size()) {
		auto [cdist, u] = *pq.begin(); pq.erase(pq.begin());
		for (auto [v, cost] : adj[u]) {
			if (d[v] <= d[u] + cost) continue;
			pq.erase({ d[v],v });
			pq.insert({ d[v] = d[u] + cost,v });
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> e;
	adj.resize(n + 1);

	for (int i = 0; i < e; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		adj[a].push_back({ b,c });
		adj[b].push_back({ a,c });
	}
	int v1, v2;
	cin >> v1 >> v2;

	int start_v1,start_v2, v1_v2, v2_v1, v1_n, v2_n;
	dijkstra(1);
	start_v1 = d[v1]; start_v2 = d[v2];
	dijkstra(v1);
	v1_n = d[n]; v1_v2 = d[v2];
	dijkstra(v2);
	v2_n = d[n]; v2_v1 = d[v1];

	long long root1 = start_v1 + v1_v2 + v2_n;
	long long root2 = start_v2 + v2_v1 + v1_n;

	if (root1<0||root2<0) {
		cout << -1;
		return 0;
	}
	if (root1 > root2) {
		if (root2 > 8000000) cout << -1;
		else cout << root2;

	}
	else {
		if (root1 > 8000000) cout << -1;
		else cout << root1;
	}

	return 0;
}

 

 

사실 넘 어려웟어요