[백준] 1504번 : 특정한 최단 경로 [C/C++]

#문제

1504번: 특정한 최단 경로

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

1504번: 특정한 최단 경로

 

---

#접근방법

이 문제는 최단거리 알고리즘 중에서 다익스트라 알고리즘을 사용하는 문제이다. 비슷한 문제로

https://rujang.tistory.com/entry/%EB%B0%B1%EC%A4%80-1753%EB%B2%88-%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-CC

[백준] 1753번 : 최단경로 [C/C++]

1753번 문제가 있는데 이 문제는 다익스트라 알고리즘을 2번 사용하여 특정정점를 지나는 최단거리를 구하면 된다.

반응형

---

#풀이

#include <stdio.h>
#include <vector>
#include <queue>
#define INF 987654321
using namespace std;

int n,e,v1,v2;
int a,b,c;
vector<pair<int,int> >node[805];
int value[805];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >pq;

void Dij(int k){
	for(int i=1;i<=n;i++)
		value[i] = INF;
	
	value[k] = 0;
	
	pq.push(make_pair(0,k));
	
	while(!pq.empty()){
		int X = pq.top().first;
		int U = pq.top().second;
		pq.pop();
		
		for(int i=0;i<node[U].size();i++){
			int V = node[U][i].first;
			int W = node[U][i].second;
			if(X+W<value[V]){
				value[V] = X+W;
				pq.push(make_pair(value[V],V));
			}
		}
	}
}

int main(){	
	scanf("%d %d",&n,&e);
	
	for(int i=0;i<e;i++){
		scanf("%d %d %d",&a,&b,&c);
		node[a].push_back(make_pair(b,c));
		node[b].push_back(make_pair(a,c));
	}
	
	scanf("%d %d",&v1,&v2);
	
	long long int v1_1,v1_v2,v1_n,v2_1,v2_n;
	
	Dij(v1);
	v1_1 = value[1];
	v1_v2 = value[v2];
	v1_n = value[n];
	Dij(v2);
	v2_1 = value[1];
	v2_n = value[n];
	
	long long int ans1 = v1_1 + v1_v2 + v2_n;
	long long int ans2 = v2_1 + v1_v2 + v1_n;
	long long int ans = ans1 < ans2 ? ans1 : ans2;
	
	if(ans>=INF) ans = -1;
	
	printf("%lld",ans);
	
	return 0;
}

 

다익스트라 알고리즘에 대한 설명은 위에있는 1753번 : 최단경로 문제를 설명한 글을 보면 된다.

 

다익스트라 알고리즘은 한 정점에서 모든 정점까지의 최단 경로를 구할 수 있다. (단, 모든 길이가 양수일 때 성립한다.)

 

해당 문제는  v1,v2를 무조건 지나야하는 1번에서 n번까지의 최단경로를 구하는 문제이다. 해당 경로는 2가지가 있다.

 

첫 번째 경로 : 1 -> v1 -> v2 -> n

두 번째 경로 : 1 -> v2 -> v1 -> n

 

v1이 시작점일 때 v1->1, v1->v2, v1->n 경로 3가지를 구할 수 있고,

v2가 시작점일 때 v2->1, v2->v1, v2->n 경로 3가지를 구할 수 있다.

 

Dij함수에 시작점을 넣어서 돌리면 시작점에서 모든 정점까지 최단경로를 구하는 다익스트라 알고리즘이 실행된다. 따라서 Dij(v1)을 넣고 경로 3가지를 저장하고, Dij(v2)를 넣고 경로 2가지를 저장해준다. (v1->v2, v2->v1는 같은 결과이므로 v2->v1경로는 생략하였다)

 

v1,v2를 지나는 경로 2가지를 ans1,ans2에 저장시켜주고 2가지 경로 중에서 작은 값을 ans에 저장시켜준다.

 

만약 그러한 경로가 없다면 ans에 INF 이상의 값이 저장되어 있을 것이므로 -1을 넣어주어서 예외처리를 시켜준다.

 

ans를 출력하면 정답이다.

---

#성능

---

#정리

최단 경로 알고리즘 중에서 다익스트라 알고리즘을 사용한다는 것,

 

특정한 정점 2개를 지나는 최단경로가 총 2가지 방법이 있다는 사실을 안다는 것,

 

이를 구하기 위해서 다익스트라 알고리즘을 2번 사용하여 구할 수 있다는 것을 알고 있으면 풀 수 있는 문제였다.