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

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

1504번: 특정한 최단 경로

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
#define INF 1e9+7

//typedef pair<int, int> p;
#define p pair<int, int>
int N, E; // (2 ≤정점N ≤ 800, 0 ≤간선E ≤ 200,000) 
int v1, v2; // 꼭 거쳐야 하는 정점 
vector<p> graph[801];
vector<int> dist;


int dijkstra(int st, int ed){
	dist = vector<int>(N+1, INF);
	priority_queue<p, vector<p > , greater<p > >pq; 
	// 최소값부터 pop하기 위한 작업 
	pq.push(make_pair(0, st));
	
	dist[st] = 0; 
	
	while(!pq.empty()){
		int now = pq.top().second; // 최소값 
		int w = pq.top().first; 
		pq.pop();
		
		if(w > dist[now]) continue;
		
		for(int i=0;i<graph[now].size(); i++){
			int next = graph[now][i].second;
			int next_w = graph[now][i].first + w;
			
			if (next_w < dist[next]){
				dist[next] = next_w;
				pq.push(make_pair(next_w, next));
			}
		}
	}
	
	return dist[ed];
}

int main(){
	cin >> N >> E;
	int a, b, c;
	int gov1, gov2;
	for (int i=0;i<E;i++){
		cin >> a >> b >> c;
		graph[a].push_back(make_pair(c, b));
		graph[b].push_back(make_pair(c, a));
	}
	cin >> v1 >> v2; 
	
	int a1 = dijkstra(1, v1);
	int a2 = dijkstra(v1, v2);
	int a3 = dijkstra(v2, N);
	if (a1 == INF || a2 == INF || a3 == INF) gov1 = INF;
	else gov1 = a1 + a2 + a3;
	
	int b1 = dijkstra(1, v2);
	int b2 = dijkstra(v2, v1);
	int b3 = dijkstra(v1, N);
	if (b1 == INF || b2 == INF || b3 == INF) gov2 = INF;
	else gov2 = b1 + b2 + b3;
	
	if (gov1 == INF && gov2 == INF) cout << -1;
	else cout << min(gov1, gov2);
}

 

- 2,3은 꼭 지나야하는 정점이므로 정점1부터 시작해 N으로 끝나야 한다는 문제 조건에 의해 두가지 방법이 나올 수 잇다.

- 각 방법에 대해 경로를 하나씩 끊어서 다익스트라 알고리즘을 구현한 함수에 적용해 최단경로를 구해준다.

- 가중치 배열 dist의 ed인덱스를 살펴봐야 한다 (빨간색으로 표시)

- 각 배열의 값을 더하고 적은 값이 이 문제의 정답이 된다.

 

 

 

// 참고 
// https://hyeo-noo.tistory.com/161