백준 1504번 : 특정한 최단 경로

문제 링크 : www.acmicpc.net/problem/1504

내 풀이(2021.1.25.) : 다익스트라

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

#define MAX_V 800 // 노드 개수의 최대값

int V, E, start_v; // V : 노드의 개수, E : 간선의 개수, start_v : 시작 노드
vector<pair<int, int>> VE_info[MAX_V + 1]; // V개의 노드들에 대한 <연결 노드, 간선 값> 쌍 (second = 특정 노드로부터 first번 노드까지의 간선값)
vector<int> shortest_distance(MAX_V + 1, INT_MAX); // 시작 노드로부터 V개의 도착 노드들까지의 최단 거리

void dijkstra(int start_v) { // 다익스트라
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
	// 최단 거리 비교를 위해 최소힙 사용 : <최단 거리, 노드 번호> 쌍 저장 및 정렬

	// 시작 노드의 최단 거리 확정
	shortest_distance[start_v] = 0; // 최단 거리 갱신
	heap.push(make_pair(0, start_v)); // 최단 거리 비교를 위해 <최단 거리, 노드 번호> 쌍을 힙에 삽입

	while (!heap.empty()) { // 모든 노드를 검사할 때까지
		pair<int, int> EV_info = heap.top(); heap.pop(); // 힙 내에서 최단 거리(first)가 가장 작은 <최단 거리, 노드 번호> 쌍
		int vertex = EV_info.second; // 도착 노드
		int distance = EV_info.first; // (현재로서의) 최단 거리
		if (distance > shortest_distance[vertex]) continue; // 이미 검사한 노드라면 무시
		
		// (continue문 아래 코드는 시작 노드를 제외한 나머지 V - 1개의 노드들에 대해 1번 수행)

		// vertex번 노드의 최단 거리 확정
		vector<pair<int, int>> info = VE_info[vertex]; // vertex번 노드에 대한 <연결 노드, 간선 값> 쌍
		for (int i = 0; i < info.size(); i++) {
			int v = info[i].first; // 연결 노드(v번 노드)
			int e = info[i].second; // 'vertex번 노드 -> v번 노드'의 간선값
			int new_dist = distance + e; // 최단 거리의 후보가 될 값
			if (new_dist < shortest_distance[v]) { // 최단 거리 갱신 여부 확인
				shortest_distance[v] = new_dist; // 최단 거리 갱신
				heap.push(make_pair(new_dist, v)); // 최단 거리 비교를 위해 <최단 거리, 노드 번호> 쌍을 힙에 삽입
			}
		}
	}
}

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

	cin >> V >> E;
	// 노드/간선 정보 초기화
	for (int i = 0; i < E; i++) {
		int u, v, w; cin >> u >> v >> w;
		VE_info[u].push_back(make_pair(v, w));
		VE_info[v].push_back(make_pair(u, w));
	}

	int v1, v2; cin >> v1 >> v2;
	
	int v_list1[4] = { 1,v1,v2,V };
	int total1 = 0;
	for (int j = 0; j < 3; j++) {
		for (int i = 0; i < V; i++) shortest_distance[i + 1] = INT_MAX;
		dijkstra(v_list1[j]);
		if (shortest_distance[v_list1[j + 1]] == INT_MAX){
			total1 = INT_MAX;
			break;
		}
		total1 += shortest_distance[v_list1[j + 1]];
	}

	int v_list2[4] = { 1,v2,v1,V };
	int total2 = 0;
	for (int j = 0; j < 3; j++) {
		for (int i = 0; i < V; i++) shortest_distance[i + 1] = INT_MAX;
		dijkstra(v_list2[j]);
		if (shortest_distance[v_list2[j + 1]] == INT_MAX) {
			total2 = INT_MAX;
			break;
		}
		total2 += shortest_distance[v_list2[j + 1]];
	}

	int answer = min(total1, total2);
	if (answer != INT_MAX) cout << answer;
	else cout << -1;

	return 0;
}

주의 사항 : 

- 1 → v1 → v2 → N인 경우 뿐만 아니라, 1 → v2 → v1 → N인 경우도 count 해서 둘 중 작은 값을 선택해야 한다.

- 이때 유의할 것으로, v1==N인 경우와 v2==1인 경우도 테스트 케이스에 포함되어 있으므로 count 해야 한다.