살짝 응용 다익스트라 (살응다)

다를 조금 응용해볼까?

문제

방향성이 없는 그래프가 주어진다. 세준이는 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)

출력

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

문제 아이디어

문제의 요점은 주어진 v1과 v2를 지나는 최단 경로의 길이를 출력하는 것이다. 또한, 1번에서 출발하여 N번 도착지로 가는 방향도 정해져있다. 우리는 도착지까지 가는 사이에 저 2개의 경로를 껴넣으면 된다.
주어지는 경로지는 중복이 되지 않음으로, 다음과 같이 2가지의 방법이 있다는 것을 알 수 있다.
- 1) 출발지 -> v1 -> v2 -> 도착지
- 2) 출발지 -> v2 -> v1 -> 도착지
1번의 경우를 봤을 때, v1을 가는데 도중에 v2가 있어서 왔다갔다 하는 반례가 있지 않냐? 라고 할 수 있는데, 그것의 경우는 2번에서 카운트를 해주기 때문에 생각할 필요가 없다.
따라서 우리는 1번의 경우와 2번의 경우를 구해서, 더 작은 값을 가져가면 답을 얻을 수 있다.

문제 풀이

우리가 해야 될 일은 위에서 명시해 놓은 1) 과 2) 를 코드로 구현하면 된다. 최단거리를 구하는 방법은 다익스트라 를 참고하면 된다.
- 출발지를 기준으로 다익스트라
- v1을 기준으로 다익스트라
- v2를 기준으로 다익스트라
15번째 줄부터 시작하는vector<ll> djk(int startNode) 함수는 다익스트라를 구하는 함수이다.
53~55번째 줄부터는 위의 3가지 다익스트라 비용을 저장하는 벡터이다.
만약에 저 중에 하나라도 INF와 같은 값이 나온다는 것은, 경로가 없다는 것을 뜻한다.
문제가 어려운 것처럼 보이지만!? 사실은 짜장면에 고추가루 뿌리는 느낌의 그런,,,, 알죠?

Code

	#include <iostream>
	#include <vector>
	#include <map>
	#include <queue>
	#include <algorithm>
	#define ll long long
	#define INF 987654321
	#define pii pair<long long, int>
	using namespace std;

	int N, E;
	int v1, v2;
	map<int, vector<pii>> adjList;

	vector<ll> djk(int startNode){
	priority_queue<pii, vector<pii>, greater<pii>> PQ;
	vector<ll> costVec(N+1); fill(costVec.begin(), costVec.end(), INF);
	vector<int> visitVec(N+1); fill(visitVec.begin(), visitVec.end(), 0);

	PQ.push({0, startNode});
	costVec[startNode] = 0;

	while (!PQ.empty()){
	int popC, popN;
	tie(popC, popN) = PQ.top(); PQ.pop();
	if (visitVec[popN] == 1) continue;
	visitVec[popN] = 1;
	for (auto& it: adjList[popN]){
	int nextC, nextN;
	tie(nextN, nextC) = it;
	if (visitVec[nextN] == 0){
	if (costVec[nextN] > costVec[popN] + nextC) {
	costVec[nextN] = costVec[popN] + nextC;
	PQ.push({costVec[nextN], nextN});
	}
	}
	}
	}
	return costVec;
	}

	int main(){
	ll answer = INF;
	cin >> N >> E;
	for (int i=0; i<E; i++){
	int a, b, c;
	cin >> a >> b >> c;
	adjList[a].push_back({b,c});
	adjList[b].push_back({a,c});
	}
	cin >> v1 >> v2;

	vector<ll> sGraph = djk(1);
	vector<ll> v1Graph = djk(v1);
	vector<ll> v2Graph = djk(v2);

	ll r1, r2, r3;

	// 1 -> v1 -> v2 -> N
	r1 = sGraph[v1];
	r2 = v1Graph[v2];
	r3 = v2Graph[N];
	if (r1 != INF && r2 != INF && r3 != INF){
	answer = r1 + r2 + r3;
	}

	// 1 -> v2 -> v1 -> N
	r1 = sGraph[v2];
	r2 = v2Graph[v1];
	r3 = v1Graph[N];
	if (r1 != INF && r2 != INF && r3 != INF){
	answer = answer > r1+r2+r3 ? r1+r2+r3 : answer;
	}

	if (answer != INF){
	cout << answer << '\n';
	}
	else{
	cout << -1 << '\n';
	}
	}

view raw main.cpp hosted with ❤ by GitHub

오늘의 Tip!

너 for문 문제있어?

Python을 해본 사람이라면, Python 문법중에 for num in num_list 의 편리성을 알 것이다. 인덱스로 하나하나 접근하지 않고, 바로 원소를 뽑아낼 수 있는 for 문 말이다! C++ 에도 있다! 절망하지 마라! C++에서는 다음과 같은 문법을 통해 원소를 뽑아낼 수 있다.

	#include <iostream>
	#include <vector>
	#include<algorithm>
	using namespace std;


	int main(){
	//5크기의 벡터 만들고 4로 초기화
	vector<int> numVector(5);
	fill(numVector.begin(), numVector.end(), 4);

	for (auto& num : numVector){
	cout << num << ' ';
	} cout << endl;


	//5크기의 pair 벡터 만들고 4로 초기화
	vector<pair<int, int>> pairVector = {{4,4},{4,4},{4,4},{4,4},{4,4}};


	for (auto& it : pairVector){
	cout << it.first << ':' << it.second << ' ';
	}cout << endl;

	}